数据结构排序算详解（动态图+代码描述）

目录

1、直接插入排序（升序）

2、希尔排序（升序） 

3、选择排序（升序）

方式一（一个指针）

方式二（两个指针）

4、堆排序（升序）

 5、冒泡排序（升序）

6、快速排序 （升序）

方式一（Hoare方法）

方式二（挖坑法） 

 快排改进算法（三数取中）

7、归并排序

8、总结

---

1、直接插入排序（升序）

描述：对于一个数组i从第二个数据开始比较，j=i-1，j<0停止，每次i下标元素放到临时变量tmp中与j下标比较，如果大于j下标，tmp还放回原位置，i和j都加加，如果小于j下标，j--,直到找到大于j下标元素，tmp放到j+1下标

时间复杂度：最好情况下O(n),最坏情况O(n^2)

空间复杂度：O（1）

//直接插入排序
//时间复杂度：最好情况下O(n),最坏情况O(n^2)
public class Test1 {public static void sort(int []array){for (int i = 1; i <array.length ; i++) {int tmp=array[i];int j = i-1;for (; j >=0 ; j--) {if(tmp<array[j])array[j+1]=array[j];else break;}array[j+1]=tmp;}}
}

2、希尔排序（升序） 

描述：我们先对数组中数据分组，数组长度即位N,具体先分为gap组，gap=N/2,N/4,N/8.....1。然后对每一组直接插入排序。

时间复杂度：O(n*log2（N)）,空间复杂度：O（1）

每种颜色一组例如：

例如：

public static void ShellSort(int [] array){int gap=array.length;//10while (gap>1){gap=gap/2;Sort(array,gap);//5,2,1}}private static void Sort(int [] array,int gap){for (int i = gap; i <array.length ; i++) {int tmp=array[i];int j = i-gap;//每组直接插入排序for (; j >=0 ; j=j-gap) {if (tmp<array[j])array[j+gap]=array[j];else break;}array[j+gap]=tmp;}

3、选择排序（升序）

方式一（一个指针）

描述： 每次找最小值下标，与i下标交换，i++

空间复杂度：O（1），时间复杂度：O(N^2)

 public static void selcetSort(int [] array){for (int i = 0; i <array.length ; i++) {int min=i;//记录每次最小值下标for (int j = i+1; j <array.length ; j++)if (array[j]<array[min])min=j;swap(min,i,array);}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

方式二（两个指针）

思路：left,right指向数组的两端，每次遍历找到最大值和最小值，分别赋值给lefgt和right

 public static void selectSort2(int[] array) {int left = 0;int right = array.length-1;int i;while (left < right) {//i  minIndex   maxIndexint minIndex=left,maxIndex=right;i=left+1;for(;i<right;i++){if (array[i]<=array[minIndex])minIndex=i;if (array[i]>array[maxIndex])maxIndex=i;}swap(left,minIndex,array);swap(right,maxIndex,array);left++;right--;}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

4、堆排序（升序）

思路：先创建成大根堆，每次排序把根节点与最后位置元素交换后向下调整，下一次根节点与end-1下标交换后向下调整，直到end<0;结束

 public static void HeapSort(int[]array){creatHeap(array.length,array);//创建大根堆int end=array.length-1;while (end>0){swap(end,0,array);signHeap(0,end,array);//向下调整不挑最后一个所以后减减end--;}}public static void creatHeap(int end,int [] array){int preheap;//每次的根节点for ( preheap=(end-1-1)/2;preheap>=0;preheap--){signHeap(preheap,end, array);}}//向下调整为大根堆为例private static void signHeap(int preheap,int end,int [] array){//向下调整int child=preheap*2+1;//preheap左子树下标while (child<end){if(child+1<end&&array[child]<array[child+1])child++;//现在child指向孩子节点的最大值if (array[preheap]<array[child]){swap(preheap,child,array);preheap=child;child=child*2+1;}else break;}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

 5、冒泡排序（升序）

 

时间复杂度:O(N^2),空间复杂度O(1)

 public static void bubbleSort(int [] array){for (int i = 0; i < array.length-1; i++) {boolean flag=false;for (int j = 0; j < array.length-1; j++) {if (array[j]>array[j+1]){swap(j,j+1,array);flag=true;}}if (flag==false)break;}}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

6、快速排序 （升序）

方式一（Hoare方法）

描述： 

每次都是最左边的元素是基点，从左边往右找到比基点大的跟从右往左找到比基点小的交换，最后left和right交点和基点交换，这样排完一次后交点左边比交点值小，后边大，分左右递归在排

时间复杂度:O(Nlog2(N)),空间复杂度O(log2(N))

    public static void quick(int [] array){int start=0,end=array.length-1;quickSort(array,start,end);}private static void quickSort(int [] array,int start,int end){if(start>=end)return;int mid=sort(array,start,end);quickSort(array,start,mid-1);quickSort(array,mid+1,end);}private static int sort(int [] array,int left,int right){int tmp=array[left];//基准int i=left;//先写右的right--，否则一遍走到left==right后与i下标交换的那一次且仅仅一次将会不有序while (left<right) {while (left < right && tmp <=array[right]) right--;//找到比tmp小的数while (left < right && tmp >= array[left]) left++;//找到比tmp大的数swap(right, left, array);}swap(left,i,array);return left;//left==right==mid}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

方式二（挖坑法） 

 思想：每次都是最左边的元素是基点，保存基点下标，此处就是一个坑，从右往左找到比基点小的放到基点下标，放到坑处 ，刚从右边放过来的元素位置就有是一个新的坑，我们再从左往右找到比基点大的元素放到新坑，当然这里又是一个坑。。。

时间复杂度:O(Nlog2(N)),空间复杂度O(log2(N))

    public static void quick(int [] array){int start=0,end=array.length-1;quickSort(array,start,end);}private static void quickSort(int [] array,int start,int end){if(start>=end)return;int mid=sort(array,start,end);quickSort(array,start,mid-1);quickSort(array,mid+1,end);}private static int sort(int [] array,int left,int right){int tmp=array[left];//基准int i=left;//先写右的right--，否则一遍走到left==right后与i下标交换后的那一次将会不有序while (left<right) {while (left < right && tmp <=array[right]) right--;//找到比tmp小的数array[left]=array[right];while (left < right && tmp >= array[left]) left++;//找到比tmp大的数array[right]=array[left];}array[left]=tmp;//最后入坑return left;//left==right==mid}

 快排改进算法（三数取中）

思想：三数取中法，index是每次左右短点和中间点第二大的数字，防止分组不太对称，成为串，这样时间复杂度变高

public static void quick(int [] array){int start=0,end=array.length-1;quickSort(array,start,end);}private static void quickSort(int [] array,int start,int end){if(start>=end)return;//三数取中法，index是每次左右短点和中间点第二大的数字//防止分组不太对称，成为串，这样时间复杂度变高int index=indexleNum(array,start,end);//快排排序开始int mid=sort(array,start,end);quickSort(array,start,mid-1);quickSort(array,mid+1,end);}//挖坑法private static int sort(int [] array,int left,int right){int tmp=array[left];//基准int i=left;//先写右的right--，否则一遍走到left==right后与i下标交换的那一次且仅仅一次将会不有序while (left<right) {while (left < right && tmp <=array[right]) right--;//找到比tmp小的数array[left]=array[right];while (left < right && tmp >= array[left]) left++;//找到比tmp大的数array[right]=array[left];}array[left]=tmp;//最后入坑return left;//left==right==mid}private static int indexleNum(int [] array,int left,int right){int index=left+((left+right)/2);//也就三个数据，空间复杂度不高，所以可以建立一个新的数组，用冒泡int [] b=new int[3];for (int i = 0; i < b.length-1; i++) {boolean flag=false;for (int j = 0; j < array.length-1; j++) {if (array[j]>array[j+1]){swap(j,j+1,array);flag=true;}}if (flag==false)break;}return b[1];}private static void swap(int i ,int j,int [] array){int tmp=array[i];array[i]=array[j];array[j]=tmp;}

7、归并排序

时间复杂度:O(Nlog2(N)),空间复杂度O(N)

 

 public static void mergerSort(int [] array){mergeFunc(array,0,array.length-1);}private static void mergeFunc(int [] array,int left,int right){if(left>=right){return;}int mid=left+((right-left)>>1);mergeFunc(array,left,mid);mergeFunc(array,mid+1,right);//左右拆分完毕，开始合并merge(array,mid,left,right);}private static void merge(int []array,int mid,int left,int right){int start1=left;int end1=mid;int start2=mid+1;int end2=right;int [] tmp=new int[right-left+1];int k=0;//保证两个表都有数据while (start1<=end1&&start2<=end2){if (array[start1]<=array[start2])tmp[k++]=array[start1++];else {tmp[k++]=array[start2++];}}//如果s2没有数据了但是s1中还有数据while (start1<=end1)tmp[k++]=array[start1++];//如果s1没有数据了但是s2中还有数据while (start2<=end2)tmp[k++]=array[start2++];//放回到原来数组for (int i = 0; i < k; i++) {array[i+left]=tmp[i];//i+left防止覆盖数据}}

8、总结