排序（7种常见排序方法）

大家好，欢迎来到IT知识分享网。

常见的排序算法：

按照插入排序分：1.直接插入排序 2.希尔排序

按照选择排序分：1.选择排序 2.堆排序

按照交换排序分：1.冒泡排序 2.快速排序

按照归并排序分：1.归并排序

常见的排序思想：是使用双指针或者三指针，在同一个数组上遍历、比较、交换。

1、直接插入排序

类比于扑克牌抽排，双指针思路。

1.时间复杂度：最坏情况下O(N^2)，如54321，最好情况下O(N)，如12345（只用i动，j不用走）

2.空间复杂度：O(1)

3.稳定性：稳定

4.使用场景：元素集合越接近有序，直接插入排序算法时间效率越高。

public void insertSort(int[] array){ //[27,15,9,18,28] for (int i = 1; i < array.length; i++) { int temp = array[i]; int j = i-1; for (; j >=0 ; j--) { if (array[j] > temp){ array[j+1] = array[j]; }else { //如果不用调整，则表示已经找到了该放的位置了 //因为前面都有序了 break; } } //当j循环走完以后，要么就是走完了所有，要么就是找到了最小位置 //所以走完以后直接把j+1的位置赋值为temp即可 array[j+1] = temp; } } 

2、希尔排序（缩小增量排序）

基本思想：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。当到达 =1时，所有记录在统一组内排好序。

时间复杂度：O(n^1.25)~O(1.6*n^1.25)

空间复杂度：O(1)

稳定性：不稳定

希尔排序的特性总结：

跳着分的目的是让交换之后，大的数都在后面，小的数都在前面。前面的这些趟都是预排序，最后1趟才是真正的排序。每一组都是插入排序，越有序越快。

public void shellSort(int[] array){ int gap = array.length; //gap表示array数组，分为多少个组 while (gap > 1){ //每次缩短一半的分组 gap /= 2; shell(array,gap); } } / * 对每组进行插入排序 * @param array * @param gap */ public void shell(int[] array,int gap) { for (int i = gap; i < array.length ; i++) { int tmp = array[i]; int j = i-gap; for (; j >=0 ; j-=gap) { if (array[j] > tmp){ array[j+gap] = array[j]; }else { break; } } array[j+gap] = tmp; } } 

3、选择排序

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

public void selectSort(int[] array){ //双指针思想 for (int i = 0; i < array.length; i++) { int miniIndex = i; for (int j = i+1; j < array.length; j++) { //如果j指向的数值小于最小值，那么就更新最小值索引 if (array[j] <= array[miniIndex]){ miniIndex = j; } } //找到最小值索引以后，就跟i位置交换 swap(array,i,miniIndex); } } 

//3指针思想 public void doubleSelectSort(int[] array){ int left = 0; int right = array.length-1; while (left < right){ int minIndex = left; int maxIndex = left; //走一趟left和right之间的值 for (int i = left + 1;i<= right;i++){ if (array[i] < array[minIndex]){ minIndex = i; } if (array[i] > array[maxIndex]){ maxIndex = i; } } //注意，如果最大值在第一个位置，会出现bug //如果最大值在下标为0的位置，此时第一个swap会把最大值换到minIndex位置上 //而第二个swap会把0位置的最小值换到数组最后一个位置，就乱了 swap(array,minIndex,left); //如果最大值的索引，正好等于left //交换完成以后，left存储的是最小值，minIndex存储的是最大值 //所以需要多加一步，将minIndex赋给maxIndex if (maxIndex == left){ maxIndex = minIndex; } swap(array,maxIndex,right); left++; right--; } } 

4、堆排序

利用堆的特性来排序。排升序是用大根堆，排降序是用小根堆。其实就是不断地将堆中的树进行向上升序或者向下排序，由于堆中的元素是大根堆或者小根堆排列的，所以最终的树就是有序的了。

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定

public void heapSort(int[] array){ //先把数组创建成堆 createHeap(array); //从最后一棵树开始排序 int end = array.length-1; while (end > 0){ swap(array,0,end); siftDown(array,0,end); end--; } } private void siftDown(int[] array,int parent, int lenght) { int child = 2 * parent + 1; while (child < lenght){ if (child + 1<lenght && array[child] < array[child+1]){ child++; } if (array[child] > array[parent]){ swap(array,child,parent); parent = child; child = 2*parent+1; }else { break; } } } private void createHeap(int[] array) { //从最后一个父亲结点开始创建 for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) { siftDown(array,parent,array.length); } } 

 5、冒泡排序

双指针

时间复杂度：O(n^2)，优化以后最好情况下可以达到O(n)

空间复杂度：O(1)

稳定性：稳定

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

6、快速排序

时间复杂度：最好的情况下，O(N*logN)，当最坏的情况下，O(N^2)，逆序或者有序

空间复杂度：O(logN)

稳定性：不稳定    

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

其实最核心的任务就是找到相交点，交换。

6.1 Hoare法

递归以后层数多了可能会栈溢出。因为怕就怕他切分的这棵树，左边长右边短，或者左边短右边长。如果是均匀切分的话，其实是效果比较好的。

private void quick(int[] array,int start,int end){ if (start >= end){ return; } //每次相遇的位置 int pivot = partitionHoare(array,start,end); //以相遇的位置作为分割点，切分以后递归继续找 quick(array,start,pivot-1); quick(array,pivot+1,end); } private int partitionHoare(int[] array, int left, int right) { //待比较元素 int tmp = array[left]; int i =left; while (left < right){ //单独的循环，不能一直减到超过左边的边界 while (left < right && array[right] >= tmp){ right--; } while (left < right && array[left] <= tmp){ left ++; } //交换left和right找到的值 swap(array,left,right); } //此时left和right都在相遇点了，将相遇点换到最前面 swap(array,i,left); return left; } 

6.2 挖坑法（Hoare衍生出来的）

        挖坑法就是把基准从数组中拿出来，数组中就留下了一个坑，然后同样从右边和左边遍历，遇到大于或者小于基准的就把那个元素，拿到坑这个位置放下，反复循环，知道左右索引相遇，就把基准填入最后一个坑里。

 private int partitionHole(int[] array,int left,int right){ //待比较元素 int tmp = array[left]; while (left < right){ //单独的循环，不能一直减到超过左边的边界 while (left < right && array[right] >= tmp){ right--; } //right找到比基准小的值，就把right所指向的元素填入left位置 //因为此时left位置就是坑 array[left] = array[right]; while (left < right && array[left] <= tmp){ left ++; } array[right] = array[left]; } array[left] = tmp; return left; }

值得注意的2个细节：

1，array[right] >= tmp 为什么要加等于？

如果不加等于，会死循环。因为left=right，left无法++right无法–，会不停地交换这两个值。

2，为什么从右边开始而不是先从左边开始？

如果先让left先走，那么走到相遇地方的时候，left指向的是一个比较大的数，此时将left和最左边交换，会让这个大的数换到最左边去。而如果是从右边先开始的话，right不断–，当遇到left的时候，right走到的是一个较小的数，此时再与最左边交换，就没问题。

6.3 前后指针法

cur用来指向比基准小的数，prev用来推着比基准大的数，cur不停地找比基准小的数，去和prev指向的比基准大的数交换。给人的感觉就是prev在不停地推着这些比基准大的数往前滚动，cur作为开路先锋去找小的数来交换。 

//前后指针法1 private int partitionBFPoint1(int[] array, int left, int right) { int prev = left ; int cur = left+1; while (cur <= right) { if(array[cur] < array[left] && array[++prev] != array[cur]) { swap(array,cur,prev); } cur++; } swap(array,prev,left); return prev; }

//前后指针法2 private int partitionBFPoint2(int[] array, int left, int right) { int d = left + 1; int pivot = array[left]; for (int i = left + 1; i <= right; i++) { if (array[i] < pivot) { swap(array, i, d); d++; } } swap(array, d - 1, left); return d - 1; }

6.4 快速排序小结

三种快速排序的方法：

1.Hoare法

2.挖坑法

3.前后指针法

这三种方法每次划分以后的序列顺序，有可能是不一样的。

当面临一个序列，要你判断他用的哪一种快速排序的方法的时候。根据以往的经验，先后检验的顺序是挖坑法、Hoare法、前后指针法。