写在前面
本文描述了常见的几种排序算法，文章可能还有很多不足，请大家谅解，欢迎大佬提意见。
本文使用到的东西
- java
1.选择排序
1. 1 算法思想
从未排序的区间中找出最小的元素，将该元素与未排序区间中第一个元素交换，第一个元素即为排序好的元素，再继续比较余下未排序的区间...
1.2 算法实现
import java.util.Arrays;
public class DSort {
public static void 选择排序(int[] list) {
int num=1;
for(int i=0;i<list.length-1;i++) {
int min=i; //记录最小元素的序号
for(int j=i+1;j<list.length;j++) {
if(list[min]>list[j]) {
min=j;
}
}
if(min!=i) {
int test=list[min];
list[min]=list[i];
list[i]=test;
System.out.println("第"+ num++ +"次排序："+Arrays.toString(list));
}
}
}
public static void main(String[] args) {
int[] list= {9,10,2,4,8,3,5,1,6,7};
选择排序(list);
}
}
1.3 执行结果
第1次排序：[1, 10, 2, 4, 8, 3, 5, 9, 6, 7]
第2次排序：[1, 2, 10, 4, 8, 3, 5, 9, 6, 7]
第3次排序：[1, 2, 3, 4, 8, 10, 5, 9, 6, 7]
第4次排序：[1, 2, 3, 4, 5, 10, 8, 9, 6, 7]
第5次排序：[1, 2, 3, 4, 5, 6, 8, 9, 10, 7]
第6次排序：[1, 2, 3, 4, 5, 6, 7, 9, 10, 8]
第7次排序：[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
第8次排序：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2.冒泡排序
2.1 算法思想
从前往后比较未排序的元素，将逆顺序的元素交换，循环比较一次之后，最后一个未排序元素即为排序好的元素，再继续从前往后比较未排序的元素...
2.2 算法实现
public class DSort {
public static void 冒泡排序(int[] list) {
int num=1;
for(int i=0;i<list.length;i++) {
for(int j=0;j<list.length-1-i;j++) {
if(list[j]>list[j+1]) {
//交换逆序元素
int test = list[j+1];
list[j+1]=list[j];
list[j]=test;
System.out.println("第"+ num++ +"次排序："+Arrays.toString(list));
}
}
}
}
public static void main(String[] args) {
int[] list= {9,10,2,4,8,3,5,1,6,7};
冒泡排序(list);
}
}
2.3 执行结果
第1次排序：[9, 2, 10, 4, 8, 3, 5, 1, 6, 7]
第2次排序：[9, 2, 4, 10, 8, 3, 5, 1, 6, 7]
第3次排序：[9, 2, 4, 8, 10, 3, 5, 1, 6, 7]
第4次排序：[9, 2, 4, 8, 3, 10, 5, 1, 6, 7]
第5次排序：[9, 2, 4, 8, 3, 5, 10, 1, 6, 7]
第6次排序：[9, 2, 4, 8, 3, 5, 1, 10, 6, 7]
第7次排序：[9, 2, 4, 8, 3, 5, 1, 6, 10, 7]
第8次排序：[9, 2, 4, 8, 3, 5, 1, 6, 7, 10]
第9次排序：[2, 9, 4, 8, 3, 5, 1, 6, 7, 10]
第10次排序：[2, 4, 9, 8, 3, 5, 1, 6, 7, 10]
第11次排序：[2, 4, 8, 9, 3, 5, 1, 6, 7, 10]
第12次排序：[2, 4, 8, 3, 9, 5, 1, 6, 7, 10]
第13次排序：[2, 4, 8, 3, 5, 9, 1, 6, 7, 10]
第14次排序：[2, 4, 8, 3, 5, 1, 9, 6, 7, 10]
第15次排序：[2, 4, 8, 3, 5, 1, 6, 9, 7, 10]
第16次排序：[2, 4, 8, 3, 5, 1, 6, 7, 9, 10]
第17次排序：[2, 4, 3, 8, 5, 1, 6, 7, 9, 10]
第18次排序：[2, 4, 3, 5, 8, 1, 6, 7, 9, 10]
第19次排序：[2, 4, 3, 5, 1, 8, 6, 7, 9, 10]
第20次排序：[2, 4, 3, 5, 1, 6, 8, 7, 9, 10]
第21次排序：[2, 4, 3, 5, 1, 6, 7, 8, 9, 10]
第22次排序：[2, 3, 4, 5, 1, 6, 7, 8, 9, 10]
第23次排序：[2, 3, 4, 1, 5, 6, 7, 8, 9, 10]
第24次排序：[2, 3, 1, 4, 5, 6, 7, 8, 9, 10]
第25次排序：[2, 1, 3, 4, 5, 6, 7, 8, 9, 10]
第26次排序：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
3.插入排序
3.1 算法思想
最初认为第一个元素是一个有序的元素区间，将有序元素区间中比未排序区间中第一个元素大的元素全部后移一位，再用未排序元素区间的第一个元素补充空缺。循环以上步骤，直到未排序区间为空。
3.2 算法实现
import java.util.Arrays;
public class DSort {
public static void 插入排序(int[] list) {
int num=1;
for(int i=1;i<list.length;i++) {
int test=list[i];
int j=i-1;
while(j>=0 && list[j]>test) {
list[j+1]=list[j];
j--;
}
list[j+1]=test;
System.out.println("第"+ num++ +"次排序："+Arrays.toString(list));
}
}
public static void main(String[] args) {
int[] list= {9,10,2,4,8,3,5,1,6,7};
插入排序(list);
}
}
3.3 执行结果
第1次排序：[9, 10, 2, 4, 8, 3, 5, 1, 6, 7]
第2次排序：[2, 9, 10, 4, 8, 3, 5, 1, 6, 7]
第3次排序：[2, 4, 9, 10, 8, 3, 5, 1, 6, 7]
第4次排序：[2, 4, 8, 9, 10, 3, 5, 1, 6, 7]
第5次排序：[2, 3, 4, 8, 9, 10, 5, 1, 6, 7]
第6次排序：[2, 3, 4, 5, 8, 9, 10, 1, 6, 7]
第7次排序：[1, 2, 3, 4, 5, 8, 9, 10, 6, 7]
第8次排序：[1, 2, 3, 4, 5, 6, 8, 9, 10, 7]
第9次排序：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
4.希尔排序
4.1 算法思想
希尔排序也叫缩小增量排序，先将待排序区间分为，多个交叉的待排序序列，每个序列执行插入排序。再将序列数量减少，直到序列数量为1.
4.2 算法实现
import java.util.Arrays;
public class DSort {
public static void 希尔排序(int[] list) {
int num=1;
int n=list.length/2; //初始序列数
while(n>=1) {
for(int i=0;i<n;i++) { //每个序列执行插入排序
for(int j=i+n;j<list.length;j+=n) {
int test=list[j];
int k=j-n;
while(k>=0 && list[k]>test) {
list[k+n]=list[k];
k-=n;
}
list[k+n]=test;
}
System.out.println("第"+ num++ +"次排序："+Arrays.toString(list));
}
n/=2; //序列数减半
}
}
public static void main(String[] args) {
int[] list= {9,10,2,4,8,3,5,1,6,7};
希尔排序(list);
}
}
4.3 执行结果
第1次排序：[3, 10, 2, 4, 8, 9, 5, 1, 6, 7]
第2次排序：[3, 5, 2, 4, 8, 9, 10, 1, 6, 7]
第3次排序：[3, 5, 1, 4, 8, 9, 10, 2, 6, 7]
第4次排序：[3, 5, 1, 4, 8, 9, 10, 2, 6, 7]
第5次排序：[3, 5, 1, 4, 7, 9, 10, 2, 6, 8]
第6次排序：[1, 5, 3, 4, 6, 9, 7, 2, 10, 8]
第7次排序：[1, 2, 3, 4, 6, 5, 7, 8, 10, 9]
第8次排序：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
5.归并排序
5.1 算法思想
将数组分解为小的区间，先使小区间有序，再合并小区间。
5.2 算法实现
import java.util.Arrays;
public class DSort {
//test为暂存数组
public static void 归并排序(int[] list,int[] test,int start,int end) {
if(end<=start) return;
int local=(start+end)/2;
归并排序(list,test,start,local);
归并排序(list,test,local+1,end);
int p1=start,p2=local+1,k=start;
while(p1<=local && p2<=end) {
if(list[p1]<list[p2]) {
test[k++]=list[p1++];
}else {
test[k++]=list[p2++];
}
}
while(p1<=local) {
test[k++]=list[p1++];
}
while(p2<=end) {
test[k++]=list[p2++];
}
for(int i=start;i<=end;i++) {
list[i]=test[i];
}
System.out.println(Arrays.toString(list));
}
public static void main(String[] args) {
int[] list= {9,10,2,4,8,3,5,1,6,7};
归并排序(list,new int[list.length],0,list.length-1);
}
}
5.3 执行结果
[9, 10, 2, 4, 8, 3, 5, 1, 6, 7]
[2, 9, 10, 4, 8, 3, 5, 1, 6, 7]
[2, 9, 10, 4, 8, 3, 5, 1, 6, 7]
[2, 4, 8, 9, 10, 3, 5, 1, 6, 7]
[2, 4, 8, 9, 10, 3, 5, 1, 6, 7]
[2, 4, 8, 9, 10, 1, 3, 5, 6, 7]
[2, 4, 8, 9, 10, 1, 3, 5, 6, 7]
[2, 4, 8, 9, 10, 1, 3, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
6.快速排序
6.1 算法思想
选择一个数做基准，通过位移实现基准左侧全部比基准小，基准右侧全部比基准大。然后分别将基准左右侧递归。
6.2 算法实现
import java.util.Arrays;
public class DSort {
public static void 快速排序(int[] list,int start,int end) {
if(start>=end) return;
int base=list[start]; //第一个数设置为基准
int i=start,j=end;
while(i<j) {
while(i<j && list[j]>base) {
j--;
}
if(i<j) list[i++]=list[j];
while(i<j && list[i]<base) {
i++;
}
if(i<j) list[j--]=list[i];
}
list[i]=base;
System.out.println(Arrays.toString(list));
快速排序(list,start,i-1);
快速排序(list,i+1,end);
}
public static void main(String[] args) {
int[] list= {9,10,2,4,8,3,5,1,6,7};
快速排序(list,0,list.length-1);
}
}
6.3 执行结果
[7, 6, 2, 4, 8, 3, 5, 1, 9, 10]
[1, 6, 2, 4, 5, 3, 7, 8, 9, 10]
[1, 6, 2, 4, 5, 3, 7, 8, 9, 10]
[1, 3, 2, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7.堆排序
7.1 算法思想
将数组构成一个类似完全二叉树的堆，并初始化为最大堆（递增排序），再将根节点与堆的最后一个节点交换，则该节点即为以排序节点，不再计入堆的范围，堆长度减1。循环以上步骤，重新构建最大堆，直到堆长度为1。
7.2 算法实现
import java.util.Arrays;
public class DSort {
public static void Adjust(int[] list,int i,int lenght) {
int max=i; //存储最大值下标
int left=i*2+1; //i*2+1为左孩子下标
int right=i*2+2; //i*2+2为右孩子下标
//左孩子存在，且比父节点大
if(left<lenght && list[left]>list[max]) {
max=left;
}
//右孩子存在，且比最大值大
if(right<lenght && list[right]>list[max]) {
max=right;
}
if(max!=i) { //最大值不是父节点，交换值
int test=list[i];
list[i]=list[max];
list[max]=test;
//交换值破坏了子树结构，递归构建最大堆
Adjust(list, max, lenght);
}
}
public static void 堆排序(int[] list) {
int num=1;
//list.length/2-1为最后一个非叶子节点下标
for(int i=list.length/2-1;i>=0;i--) {
Adjust(list, i, list.length); //构建最大堆
System.out.println("第"+ num++ +"次排序："+Arrays.toString(list));
}
for(int i=list.length-1;i>0;i--) {
int test=list[i];
list[i]=list[0];
list[0]=test;
Adjust(list, 0, i); //重新构建最大堆
System.out.println("第"+ num++ +"次排序："+Arrays.toString(list));
}
}
public static void main(String[] args) {
int[] list= {9,10,2,4,8,3,5,1,6,7};
堆排序(list);
}
}
7.3 执行结果
第1次排序：[9, 10, 2, 4, 8, 3, 5, 1, 6, 7]
第2次排序：[9, 10, 2, 6, 8, 3, 5, 1, 4, 7]
第3次排序：[9, 10, 5, 6, 8, 3, 2, 1, 4, 7]
第4次排序：[9, 10, 5, 6, 8, 3, 2, 1, 4, 7]
第5次排序：[10, 9, 5, 6, 8, 3, 2, 1, 4, 7]
第6次排序：[9, 8, 5, 6, 7, 3, 2, 1, 4, 10]
第7次排序：[8, 7, 5, 6, 4, 3, 2, 1, 9, 10]
第8次排序：[7, 6, 5, 1, 4, 3, 2, 8, 9, 10]
第9次排序：[6, 4, 5, 1, 2, 3, 7, 8, 9, 10]
第10次排序：[5, 4, 3, 1, 2, 6, 7, 8, 9, 10]
第11次排序：[4, 2, 3, 1, 5, 6, 7, 8, 9, 10]
第12次排序：[3, 2, 1, 4, 5, 6, 7, 8, 9, 10]
第13次排序：[2, 1, 3, 4, 5, 6, 7, 8, 9, 10]
第14次排序：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
8.总结
对时间复杂度、空间复杂度计算还是不够擅长，只能到时候再补充，希尔排序、堆排序稍微有些复杂，没有图片说明会比较难理解一些。可以复制代码运行帮助理解。有不清楚的地方欢迎评论留言，看到的我都会回复的。本文到此结束，有什么不足的地方请大家不吝指正。