一、常见的排序算法

本篇将会介绍八种非常常见的排序算法，前七种是基于比较的排序算法，包括直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序，对应本文标题里的前七个排序算法。
最后一个计数是指计数排序，又称鸽巢原理，相对于前七种，它是非比较排序，是对哈希直接定址法的变形应用。

其中冒泡排序和堆排序在前面的相关文章中已经分享过了，下面来简单回顾一下。
注：本篇不特别说明默认以排升序为例实现各排序算法

二、常见排序算法的实现

这里分享一个演示算法动态效果的网站Comparison Sorting Visualization。

有不理解的可以结合动态演示观察分析。

2.1 排序算法回顾

2.1.1 冒泡排序

冒泡排序的基本思想是：多次遍历数组，每次遍历依次比较相邻元素，将较大值不断交换到后面，每趟遍历确定一个最大值，对于大小为n的数组至多遍历n-1趟就可以确定n个值。

动态效果如下：

这里的效果很像鱼儿在水里吐泡泡，大泡泡先浮上水面，小一点的泡泡后浮上水面，更小一点的泡泡最后浮上水面。

那么我们如何实现冒泡排序算法呢？
如下：

// 冒泡排序
// 时间复杂度：O(N^2) 最好情况：O(N) 空间复杂度：O(1)
void BubbleSort(int* a, int n)// a代表数组，n代表数组长度
{// i代表趟数，n个数据，最多需要n-1趟for (int i = 0; i < n - 1; i++){// flag检测单趟冒泡中是否发生交换，如果单趟冒泡中一次交换都没有，说明数组已经有序// 可判断flag的状态决定是否提前结束冒泡排序，提高算法效率int flag = 0;// a[j-1],a[j]代表单趟冒泡中的相邻元素，从[0],[1]开始// 由于1趟冒泡确定一个最大值，因此每趟冒泡可以去掉一个后面已经确定位置的元素// 所以j的最大值=最大趟数-当前趟数-1（最大趟数=n-1，当前趟数=i+1）for (int j = 1; j < n - i; j++){// 遍历比较相邻元素，较大者交换到后面if (a[j - 1] > a[j]){Swap(&a[j - 1], &a[j]);flag = 1;// 交换发生，flag置为1}}if (flag == 0) break;// flag等于0代表单趟冒泡中未发生交换，数组有序，提前结束}
}

2.1.2 堆排序

堆是一棵以顺序结构存储的完全二叉树，且这棵完全二叉树的所有子树都满足root<=left && root<=right或root>=left && root>=right，例如：
小堆：大堆：

对于堆，我们按照从上到下，从左到右的方式读取就是它的实际存储结构了。例如上面的小堆是按10,20,55,25,30,60存储，上面的大堆是按70,50,30,25,15,5存储。反过来，对于任意数组，依次读取数据，可以转化为二叉树结构，如果二叉树符合堆结构，那就可以进行堆排序了。
之前提过，堆排序分为两个步骤：

1. 建堆
   • 升序：建大堆
   • 降序：建小堆
2. 利用堆删除思想来进行排序

所谓建堆，实际上是因为任意数组中，数据的初始顺序并不符合我们需要的堆结构的顺序，所以我们需要先进行建堆操作，将数组中的数据先调整为符合堆结构的顺序。例如数组arr[7] = { 20,25,55,50,30,60,5 }，不经“建堆”就直接转化成二叉树的话如下：

先调整数组arr[7]中数据的初始顺序20,25,55,50,30,60,5，变成符合堆结构的顺序5,25,20,50,30,60,55，再转化成二叉树就符合堆的定义了。

堆排序实现示例如下：

void AdjustDown(int* a, int n, int root)// 向下调整算法
{int child = 2 * root + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]) child++;// “<”建小堆排降序；“>”建大堆排升序if (a[child] > a[root])// “>”建小堆排降序；“<”建大堆排升序{Swap(&a[root], &a[child]);root = child;child = 2 * root + 1;}else{break;}}
}
// 堆排序
// 时间复杂度：O(N*lgN) 空间复杂度：O(1)
void HeapSort(int* a, int n)
{// 排升序建大堆O(N)for (int i = (n - 2) / 2; i >= 0; i--){AdjustDown(a, n, i);}// 排序O(N*lgN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

建堆操作以及排序操作的实现主要靠的是向下调整算法，具体内容请见博主的上一篇博客《数据结构修炼——树？二叉树？堆？从入门到代码实现，第一弹！！！》。

2.2 直接插入排序

直接插入排序的核心思想是：取数组有序区间后一元素依次与数组有序区间中的元素依次比较并插入，使数组的有序区间不断扩大。

这句话是什么意思呢？数组的有序区间指什么？我们设想一下，一个数是有序的吗？答案是肯定的，当然是有序的。那对于任意非空数组，我们是否可以认为a[0]也是它的有序区间？如果a[0]是它的有序区间，那我们不就可以取有序区间后一元素——a[1]，与有序区间中的元素依次比较然后插入合适位置，插入后有序区间不就扩大成a[0]到a[1]了，我们接着选a[2]继续比较并插入有序区间，不断重复，直到完成整个数组的排序即可，这就是插入排序的核心内容。

再以序列5,4,3,1,2为例，假定有序序列为a[0]到a[end]（0 <= end < 4，end初始为0）.

1. end = 0，有序序列：a[0]=5，取a[end+1]=a[1]=4与有序序列比较。4小于a[0]=5，序列元素a[0]向后覆盖，序列变为5 5 3 1 2。有序序列比较完还未插入，直接插入a[0]处，有序序列变为4 5 3 1 2，end++；

2. end = 1，有序序列：a[0]=4 a[1]=5，取a[end+1]=a[2]=3与有序序列比较。3小于a[1]=5，序列元素a[1]向后覆盖，序列变为4 5 5 1 2；3小于a[0]=4，序列元素a[0]向后覆盖，序列变为4 4 5 1 2。有序序列比较完还未插入，直接插入a[0]处，序列变为3 4 5 1 2，end++；

3. end = 2，有序序列：a[0]=3 a[1]=4 a[2]=5，取a[end+1]=a[2]=1与有序序列比较。1小于a[2]=5，序列元素a[2]向后覆盖，序列变为3 4 5 5 2；1小于a[1]=4，序列元素a[1]向后覆盖，序列变为3 4 4 5 2；1小于a[0]=3，序列元素a[0]向后覆盖，序列变为3 3 4 5 2。有序序列比较完还未插入，直接插入a[0]处，序列变为1 3 4 5 2，end++；

4. end = 3，有序序列：a[0]=1 a[1]=3 a[2]=4 a[3]=5，取a[end+1]=a[4]=2与有序序列比较。2小于a[3]=5，序列元素a[2]向后覆盖，序列变为1 3 4 5 5；2小于a[2]=4，序列元素a[2]向后覆盖，序列变为1 3 4 4 5；2小于a[1]=3，序列元素a[1]向后覆盖，序列变为1 3 3 4 5；2大于a[0]=1，找到合适位置，直接将2插入到上一比较元素，即a[1]处，序列变为1 2 3 4 5，end++；

5. end = 4，排序结束。数组大小为5，共计排序4趟，即n-1趟。对于任意大小为n的数组，至多直接插入排序n-1趟即可完成排序。

直接插入排序的代码示例如下：

// 直接插入排序-适应性强,越有序排序越快
// 最坏情况（逆序/序列元素都相等）：O(N^2)；最好情况（顺序）：O(N)
// 时间复杂度：O(N^2)，实际效率大多介于O(N)到O(N^2)之间
void InsertSort(int* a, int n)
{// 有序序列：[0,0]->[0,1]->...->[0,n-2]for (int i = 0; i < n - 1; i++)// i为有序序列最后一个元素的下标{int end = i;// end为比较元素的下标int tmp = a[end + 1];// tmp为插入元素// 从后往前依次比较有效序列所有元素while (end >= 0){if (tmp < a[end]){// 没找到合适位置就向后覆盖，并继续向前比较a[end + 1] = a[end];--end;}else break;// 找到合适位置就停止比较}// 比较结束，如果仍未找到插入位置，end最后为-1，直接在a[0]处插入tmp// 如果找到插入位置，end+1为上一比较元素的下标，直接插入即可a[end + 1] = tmp;}
}

直接插入排序特性总结：

1. 序列越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)

复杂度分析：容易知道，如果每次插入的值都是最小值，那么有序序列中所有元素都要向后移动一次，对于一个大小为n的数组，至多需要n-1趟完成排序，从第一趟开始，序列元素个数为1，移动次数为1；第二趟，序列元素个数为2，移动次数为2；一直到第n-1趟，移动次数为n-1。总移动次数为（1+2+…+n-1）= n*(n-1)/2，这里还可以加上n-1，代表n-1趟中每趟的插入操作，因此最坏情况下时间复杂度为O(N²)。如果数组为顺序，那么每次插入的值都大于有序序列，则移动次数都为0，但每趟结束时一定有一次在a[end+1]处赋值的操作，所以有n-1次“自己给自己赋值”的操作，因此最好情况下时间复杂度为O(N)。

2.3 希尔排序

希尔排序是对直接插入排序的一种改良。我们知道，数组越有序直接插入排序的时间复杂度就越接近O(N)，这个复杂度对于排序算法而言是非常高的。因此，希尔排序旨在先通过预排序提升数组的有序性，之后再进行直接插入排序，最终使得算法的复杂度接近O(N)。

希尔排序的实际实现采用的是缩小增量法。即假定一个变量gap，具体多大我们暂且不管，这个gap决定了我们将序列分为多少组，如下（数组大小为10，gap为5）：

如图9 4，1 8，2 6，5 3与7 5分别为一组（gap也代表每组中各元素的间隔，每组元素是跳着挑选的，例如a[5]=4与a[0]=9共间隔5个空）。预排序采用的排序方法仍然是直接插入排序，只不过跳着挑选元素分组，减少了数据量。

上图有5组数据，几组数据就需要进行多少次预排序，5组进行5趟：
初始序列为9 1 2 5 7 4 8 6 3 5，
第一趟9 4组进行直接插入排序，有序序列：9，4与有序序列比较，4与9交换，如下图。

第二趟1 8组进行直接插入排序，有序序列：1，8与有序序列比较，8与自己交换，顺序不变。
第三趟2 6组进行直接插入排序，有序序列：2，6与有序序列比较，6与自己交换，顺序不变。
第四趟5 3组进行直接插入排序，有序序列：5，3与有序序列比较，3与5交换，如下图。

第五趟7 5组进行直接插入排序，有序序列：7，5与有序序列比较，5与7交换，如下图。

观察一次预排后的序列，我们可以发现数据大的都集中在数组的后半部分，数据小的都集中在数组的前半部分，这正是预排序最终需要的效果——接近有序。

需要注意，gap选取的越大，数据间隔就越大，数据量就少，一次插入排序的消耗就越少，效率就越高；gap选取的越小，数据间隔就越小，数据量就多，效率就一定降低，但预排序后数组就更接近有序。因此，为了在保证有序性的同时兼顾效率与消耗问题，gap的选取就变成十分重要的问题了。

最开始，希尔排序算法的创造者Donald Shell提出的是gap=n/2，gap=gap/2，即进行多次预排序，同时第一次预排序的gap取n/2，之后每次取gap/2，直到gap=1，约log2ⁿ次预排序。当然，log2ⁿ次预排序有人觉得在一些情况下还是太多了，于是提出gap=n/3，gap=gap/3，即第一次预排序gap取n/3，之后每次取gap/3，直到gap=1，约log3ⁿ次预排序。

关于gap的取法很多，不过多介绍，详细可以看以下两本书：


由于Knuth进行了大量试验统计，所以取gap=n/3，gap=gap/3大多情况下还是比较合适的，注意是大多，还是有少数情况达不到最佳效率的。

至于希尔排序的时间复杂度，推荐记住O(N^1.3)即可，这是Knuth实验统计得出的大概值，有不错的信赖度。

那么如何具体实现希尔排序呢？
代码示例如下：

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保证gap最后一个值为1// gap > 1是预排序// gap == 1是直接插入排序gap = gap / 3 + 1;// 插入算法for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0 && tmp < a[end]){a[end + gap] = a[end];end -= gap;}a[end + gap] = tmp;}}
}

容易知道，当gap等于1时，就变成了直接插入排序，因此代码主要通过最外层的while循环控制希尔排序的整体流程，即：从gap较大时数据量小的预排序，到gap较小时数据量小的预排序，到最后gap==1时的直接插入排序。

以上图所示数组为例，令gap=3，分组情况如下，

我们可以选择一次性将一组数据完成直接插入排序，也可以选择多组并行的方式完成直接插入排序，例如，上述数组被分为3组，
对于i=0,i=1,i=2，分别进行直接插入排序，我们可以依次认定3个有序序列a[0]，a[1]，a[2]，分别用a[3]，a[4]，a[5]与序列a[0]，a[1]，a[2]比较并交换，变成

对于i=3,i=4,i=5，再分别进行直接插入排序，我们可以依次认定3个有序序列a[0] a[3]，a[1] a[4]，a[2] a[5]，分别用a[6]，a[7]，a[8]与序列a[0] a[3]，a[1] a[4]，a[2] a[5]比较交换。
最后还剩一个a[9]与红色组前面的有序序列比较交换，变成

一组数据的预排序其实还可以拆分成一段一段的预排序的，所以多组并行的方式同样可以实现预排序，还可以达到简化代码的效果。

2.4 选择排序

选择排序的核心思想就是假定一个最小值min，通过遍历数组进行比较，不断更新最小值，直到遍历结束，最后将真正的最小值交换到数组前面。

选择排序的实际实现，我们还可以做一个优化，那就是遍历一遍数组，我们一次找两个值，一个最小值，一个最大值。
代码示例如下：

// 选择排序-时间复杂度顺序/逆序都为O(N^2)
void Swap(int* a, int* b)// 交换数组元素
{int tmp = *a;*a = *b;*b = tmp;
}
void SelectSort(int* a, int n)
{// begin与end记录数组首尾未确定位置的元素下标，初始为0与n-1int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;// mini找最小值的下标，maxi找最大值的下标// 最小值与最大值初始为a[0]，因此从i=1开始找，找到endfor (int i = begin + 1; i <= end; i++){if (a[i] < a[mini]){// a[i]小于当前最小值就更新下标mini = i;}if (a[i] > a[maxi]){// a[i]大于当前最大值就更新下标maxi = i;}}// 找到当前最小值与最大值后，先将最小值交换到begin位置Swap(&a[begin], &a[mini]);// 为防止begin位置是最大值且被mini位置交换走，增加一个判断if (maxi == begin){maxi = mini;}// 确保maxi有效的情况下，交换maxi位置与end位置Swap(&a[end], &a[maxi]);// 首尾确定位置的元素都加1begin++;end--;}
}

2.5 快速排序

2.5.1 快速排序（霍尔法）

先来看霍尔法的快速排序（其他两种实际效果基本相同，就是具体思路与处理方式不同）。霍尔法的快排首先将数组左端元素设为key，R从数组右端开始向左查找小于key的值，找到后停止，接着left从数组左端开始向右查找大于key的值，找到后停止，R和L都找到后交换对应元素，不断重复这个过程，直到L或R相遇，最后交换key与相遇位置的值，这就是单趟快速排序的完整过程。

单趟快速排序想要实现的效果是什么呢？那就是至少确定一个值的最终位置（也就是key），同时确保小于key的值都在左边，大于key的值都在右边，重复并进行多次即可确定所有数据的位置。

以动图所示的数组为例，其初始顺序如下图：

以6为key，R先从右端向左找小于key的值，经过8、10，找到5小于key，于是R停止，L从左端向右开始找大于key的值，经过6、1、2，找到7小于key，L与R都找到后互相交换，即5和7交换。

5和7交换后如图，R与L还没有相遇，继续查找。R先走，从交换位置（即现在7所在的位置）开始向左找，找到4比key小，于是停止，换L找，L也从交换位置（即现在5所在的位置）开始，继续向右找到9比key大，L与R都找到，进行交换，即4与9交换。

4和9交换后如图，R与L还没有相遇，继续查找。R从交换位置处（即现在9所在位置）开始向左找比key小的值，找到3，停止，L从交换位置处（即现在4所在位置）开始向右找比key大的值，L向前一步到3处，发现R现在也在3的位置，于是R与L相遇，交换key值与相遇位置的值，即3与6交换。

3与6交换后如图，一趟快速排序完成。重点来了，我们观察一下完成一趟快排后的数组，此时数组中，在key——6左边的都是小于key的，在key——6右边的都是大于key的，而6所在的位置正是其最终位置。

完成到这里已经非常简单了，我们可以采用递归或者循环等方式继续对6的左右区间进行快速排序，重复进行多趟操作即可。

那么快排的奥妙是什么呢？其实就在于右边找小，左边找大，小于key——6的被找到都会被交换到左边去，大于key——6的被找到都会被交换到右边去。

大于key都在右边，小于key都在左边好理解，那为什么最后的相遇位置一定小于key呢？
其实，我们仔细分析一下数组可能存在的情况就能发现原因。
首先，我们规定R先查找，而最终相遇无非是动R时遇L或者动L时遇R。但如果是动L时遇R，那就意味着R一定已经找到小于key的值，所以这种情况能确保相遇位置小于key。
如果是动R遇L，L可能有两种情况，第一L从未动过，L还在左端的起始位置（也就是key的位置），这种情况属于key是最小值，那么R最终会一直走到key的位置与L相遇，最后key自己与自己交换，这种情况我们继续第二趟排序就是，所以也不影响；第二L不在起始位置，也就是说在这一趟快速排序中，L已经与R起码交换过一次，那么L所在的位置是上一次的交换位置，我们知道，L找大而R找小，交换后L处就变成了小，所以动R遇L最终还是会在小于key的位置。

因此，我们可以下结论：当key在左端时，右边找小，左边找大，且R先走时，R与L一定会相遇在比key小的位置。相同的，令key在右端，右边找小，左边找大，但L先走，R与L一定相遇在比key大的位置，这种方式也是可行的。

知道快速排序的底层逻辑后，我们该如何实现呢？
代码示例如下：

// a为数组，left表示数组区间的左下标，right表示右下标
void QuickSort(int* a, int left, int right)
{// 需要注意无效区间的存在可能，在开始处增加left与right的判断if (left >= right) return;// 先选定左端为keyint keyi = left;// 定义两个变量begin与end分别代表动图中的L与R，用于遍历数组int begin = left, end = right;// 开始遍历查找，单趟快排，即循环结束条件：相遇，begin==endwhile (begin < end){// R，也就是end先动，从右向左，找小。// 一直end--，直到遇见比key小的值时停止，此时end为它的下标while (begin < end && a[end] >= a[keyi]) end--;// L，也就是begin后动，从左向右，找大。// 一直begin++，直到遇见比key大的值时停止，此时begin为它的下标while (begin < end && a[begin] <= a[keyi]) begin++;// 此时R与L都查找完毕，于是交换// 当然也可能R或者L一直没找到，R与L相遇，自己交换自己Swap(&a[begin], &a[end]);// 一次查找结束，相遇就出循环，没相遇就不断查找再交换// 确保比key小的都集中在左边，比key大的都集中在右边}// 此时一趟快速排序结束，交换key值与相遇位置Swap(&a[keyi], &a[begin]);// 一趟快排结束后，继续排key的左右区间，区间划分如下// [left, keyi - 1] keyi [keyi + 1, right]QuickSort(a, left, keyi - 1);// 递归调用函数排左区间QuickSort(a, keyi + 1, right);// 递归调用函数排右区间
}

到这里，快排就完成了。当然这只是简单版本，当前的快排还存在许多缺陷，例如我们之前分析时提到的，当key为最小值，R会从右一直找到左，假使数组完全有序呢？或者前半部分有序呢？这种情况会使快排效率下降，且函数递归调用的层数更多，这会浪费更多栈空间，可能造成栈溢出。

我们从多趟的角度来看，完成一趟快排，划分左右区间，如果每次都是对半分的话，那快排的递归深度就只有log2^N，因为要先排完左区间再排右区间，而左区间有N/2个数据，左区间会不断递归下去，左区间没排完前函数栈帧就会一直占在那里，共占用log2^N。只有左区间全部排完，函数才会结束，然后再排右区间，再占用也还是log2^N。

但如果key每次都是最小值，那向下划分区间时每次就只能去掉一个key，最终要划分n次，n个数据就要递归n次，栈帧占用也为n，这就比log2^N大多了。而且当数组完全有序时，还会有2n次自己交换自己的无效操作，所以即使部分有序也无法忽视其造成的效率低下。

快排一般而言复杂度在O(N*logN)，在有序情况下就退化到O(N²)了。

所以有人提出了三数取中的优化方法。为了避免有序情况下的效率低下，提高平均效率，我们可以利用三数取中的原则，对数组首、尾、中间三处的元素进行比较，取中间值当作key，避免key一直是最小值。
代码示例如下：

int GetMidi(int* a, int left, int right)// 三数取中优化
{// 随机选keyint midi = (left + right) / 2;// 中间元素的下标// 在首、尾、中间三处，选出中间大小的元素并返回其下标if (a[left] < a[midi]){if (a[right] > a[midi]) return midi;else{if (a[left] < a[right]) return right;else return left;}}else{if (a[right] < a[midi]) return midi;else{if (a[right] < a[left]) return right;else return left;}}
}
// a为数组，left表示数组区间的左下标，right表示右下标
void QuickSort(int* a, int left, int right)
{if (left >= right) return;int midi = GetMidi(a, left, right);// midi为首、尾、中三个元素中中间大小的值的下标Swap(&a[left], &a[midi]);// 将中间值交换到数组左端// 余下流程和前面一致int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]) end--;while (begin < end && a[begin] <= a[keyi]) begin++;Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

三数取中对于快排平均效率的优化还是很大的，还有一个小区间优化也能在一定程度上提升快排效率。

递归和二叉树很像，二叉树的最底层占据了整棵树结点数量的一半，其实递归也是，往往最下面很小一个区间，也许就几个数的排序就占用了相当部分的消耗。
以5个数的快速排序为例：

单算调用与回归的次数5个数共12次，但其实根本没有必要。因此有人想出了个方法，对于区间比较小的情况，直接使用其他更方便的排序，例如直接插入排序，它的适应性强，效率也不是很低，毕竟逆序的情况属于小概率，顺序情况下其时间复杂度还能直接到O(N)，而递归不管有序，其消耗和效率都摆在那里，所以直接插入排序还是比递归更适用的。

小区间优化代码示例如下：

// 直接插入排序-适应性强,越有序排序越快
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0 && tmp < a[end]){a[end + 1] = a[end];--end;}a[end + 1] = tmp;}
}
void QuickSort(int* a, int left, int right)
{if (left >= right) return;// 小区间优化：不再递归分割排序，减少递归次数。if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);// 小区间用插入排序return;}int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]) end--;while (begin < end && a[begin] <= a[keyi]) begin++;Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

2.5.2 快速排序（挖坑法）

快速排序除了霍尔版本，还有挖坑法，它们本质上大致相同，主要是实现思路不同，我们可以简单了解一下，选择其中之一即可，按自己容易理解的思路来实现快速排序。

挖坑法与霍尔法基本一致，但是key值我们另外保存起来，这样在左端就形成了一个坑位，接着R先从右端向左找小于key的值，找到后将这个值放到坑位，于是这个值原来的位置（也就是现在的R处）就变成了新的坑位；接着L从左端向右找大于key的值，找到后将这个值放到R处的新坑位，于是L处变成新坑位；L找到了换R走，R找到了换L走，直到相遇，相遇时有两种情况，一L遇R，二R遇L，但现在不管哪种，不动的那个脚底下都是坑位（也就是无效值）所以我们可以直接将key保存到坑位中（也就是相遇位置），这就完成了一趟挖坑快排。

挖坑快排实现的效果和霍尔快排是一致的，以动图所示数组为例，一趟挖坑快排过程如下：
先将左端的6拿出来，用临时变量保存，形成坑位（无效值），如下图。

形成坑位后，R从右端向左找小于key的值，经过8、10，找到目标值5，将5甩到坑位，如下图。

R找到，换L找，L从左端向右，经过5、1、2，找到目标值7，于是将7甩到R脚底下的坑位，如下图。

L找完，还没相遇，换R继续找。R从7开始找，找到目标值4，于是将4甩到L脚底下的坑位，如下图。

R找完，换L继续找。L从4开始找，找到目标值9，于是将9甩到R脚底下的坑位，如下图。

L找完还没相遇，换R继续找。R从9开始，找到目标值3，于是将3甩到L脚底下的坑位，如下图。

R找完，换L找。L从3开始向右走，遇见R，于是查找结束，将key值6甩到坑位（相遇位置）。

一趟挖坑排序结束，同样是左区间都是小于key值6的数，右区间都是大于key值6的数，而key值6也到了其最终位置处。那我们可以再来看看霍尔版本的一趟快排结果，如下图。

我们可以发现，两种方法虽然大致相同，但对同一组数进行一趟排序后，细节上还是有所不同的，当然这并不影响最终结果，因为只要我们重复多趟排序，两种方法的最终结果还是一样的，消耗也基本相同。

挖坑法主要免去了我们对相遇位置的值大小的分析，可能相对好理解一些。

挖坑快排的代码示例如下：

// 快速排序
void QuickSort(int* a, int left, int right)
{if (left >= right) return;// 挖坑法int key = a[left];// 保存key值，而不是key的下标int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= key)--end;// a[end]给begin这个坑，end就变成了新的坑。a[begin] = a[end];while (begin < end && a[begin] <= key)++begin;// a[begin]给end这个坑，begin就变成了新的坑。a[end] = a[begin];}// R与L相遇，将key甩到相遇位置下的坑位a[begin] = key;QuickSort(a, left, keyi - 1);// 排左区间QuickSort(a, keyi + 1, right);// 排右区间
}

2.5.3 快速排序（前后指针法）

除了霍尔法和挖坑法，还有前后指针法也值得大家了解一下。

前后指针法是指，我们定义prev与cur这两个变量代表数组元素的下标，cur和prev一前一后，prev在后面，从key开始，而cur在前面，从key的下一位置开始。首先判断cur处元素是大于等于key还是小于key，如果大于或等于key，prev不动，cur向前一步；如果小于key，才让prev向前一步，再交换此时prev与cur处的值，接着cur向前一步。不断重复这个过程，直到cur遍历完所有元素，最后再让key处元素与结束时prev处元素交换，一趟前后指针快排结束。

以动图中的数组为例，一趟前后指针快排效果如下：
先令左端元素为key，再创建两个变量cur和prev一前一后，代表对应元素的下标。再对cur处元素进行判断，1小于key——6，prev先向前一步，再对cur与prev的对应元素执行交换，交换后再让cur向前一步。

完成一次比较，数组还没遍历完，继续重复上述过程。先判断cur处元素，2小于key——6，于是prev先向前一步，再交换prev与cur处元素，最后令cur向前一步。

数组还未结束，重复。比较判断cur处元素大小，7大于key——6，这时prev不动，也不交换，仅cur向前一步。到9处，9同样大于key——6，cur再向前一步，到3处。

cur到3处，对cur处元素判断，3小于key——6，于是prev先向前一步，到7处，再对prev和cur处元素进行交换，于是7与3交换，交换后再令cur向前一步。

cur处小于key——6的3被交换到prev处，prev处大于key——6的7被交换到原本的cur处，现在cur向前一步到4处。对cur处元素4判断，4小于key——6，于是prev先向前一步，到9处，再交换cur——4与prev——9，最后令cur向前一步。

cur向前一步到5处，5小于key——6，于是prev先向前一步，再交换prev——7与cur——5，cur再向前一步到10处。

判断cur处元素，10大于key——6，prev不动，不交换，仅cur向前一步，到8处。8同样大于key——6，prev还是不动，也不交换，仅cur再向前一步，数组结束，于是让key——6与prev——5交换，一趟前后指针快排结束。


这是前后指针法快排的最终效果，同样确定了key值的最终位置且左区间都小于key，右区间都大于key，而且最终实现细节与霍尔法以及挖坑法都不相同，但是多趟排序后的最终排序结果以及消耗是相同的，仅具体细节与实现思路有所差异。

前后指针法快速排序代码示例如下：

// 快速排序
void QuickSort(int* a, int left, int right)
{if (left >= right) return;// 前后指针法int keyi = left;// 选定左端元素为key值int prev = left, cur = left + 1;// prev在后，cur在前while (cur <= right)// cur遍历完数组时结束循环{if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);// cur处元素小于key时交换cur++;// 不管cur处元素大于等于还是小于key，cur都向前一步}// 一趟快排结束前，交换key与此时prev停下位置处的元素Swap(&a[prev], &a[keyi]);QuickSort(a, left, keyi - 1);// 排左区间QuickSort(a, keyi + 1, right);// 排右区间
}

这里另外解释一下这段代码：

if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);// cur处元素小于key时交换

这段代码是什么意思呢？其实我们可以发现，上面的分析过程中是存在很多自己交换自己的操作的，这个操作是可以优化的。因为我们需要实现的其实是cur小于key时prev才向前一步，然后再交换，且prev如果向前一步和cur在同一位置就不交换。
而上述代码a[cur] < a[keyi] && ++prev != cur，底层逻辑是与&&逻辑符会先从左边开始判断，也就是说会先判断a[cur] < a[keyi]是否成立，如果成立，那么就会++prev，并判断++prev后是否与cur相等，相等说明它们就指向了同一个元素，那就没必要自己交换自己了，所以即使cur小于key，而++prev后如果prev == cur那也不会交换。

2.5.4 快速排序（非递归）

前面3种方法都是递归实现的快速排序，那如何用循环而不是递归的方式实现快排呢？
很简单，快排每层递归主要控制的其实就是区间而已，我们只需要将模拟递归的顺序，将区间依次存储起来再使用即可。

模拟递归存储区间可以用栈或者队列，这里以栈为例（不了解栈或队列的可以看看我前面几篇文章）。

由于本篇主要用C语言讲解，所以先给出栈的实现代码：
头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
//栈的初始化、销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
//入栈、出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//获取栈顶数据
STDataType STTop(ST* pst);
//获取数据个数
int STSize(ST* pst);
//判空
bool STEmpty(ST* pst);

源文件

#include"Stack.h"
//栈的初始化、销毁
void STInit(ST* pst)
{assert(pst);pst->arr = NULL;pst->top = 0;pst->capacity = 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst->arr);pst->arr = NULL;pst->top = pst->capacity = 0;
}
//入栈、出栈
void STPush(ST* pst, STDataType x)
{assert(pst);//判断是否满栈决定是否扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDataType * tmp = (STDataType*)realloc(pst->arr, newcapacity * sizeof(STDataType));if (!tmp){perror("STPush::realloc fail!");return;}pst->arr = tmp;pst->capacity = newcapacity;}pst->arr[pst->top++] = x;
}
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//获取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->arr[pst->top - 1];
}
//获取数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}
//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

以数组9 5 7 4 8为例。第一层递归区间为[0,4]，我们可以先将0 4入栈。
当我们进入第一趟快排时，先从栈中取出区间，再对该区间进行快速排序，以霍尔法为例，数组被调整为4 5 9 7 8。key被交换到中间，调整keyi = 2。
区间划分为：[left, keyi-1] keyi [keyi+1, right]——[0, 1] 2 [3, 4]。

void QuickSort(int* a, int left, int right)
{if (left >= right) return;int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]) end--;while (begin < end && a[begin] <= a[keyi]) begin++;Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);QuickSort(a, left, keyi - 1);// 排左区间QuickSort(a, keyi + 1, right);// 排右区间
}

在一个区间完成一次快速排序时，我们可以先将这个区间拆分出来的右区间入栈，再将这个区间拆分出来的左区间入栈。
如[0, 4]排完，它拆分出来的左右区间分别是[0,1]和[3,4]，我们可以先将[3,4]入栈，再将[0,1]入栈。这样后面取的时候就能先取到左区间了，排序就是按照先排左再排右的顺序了。整体流程就是上一层带下一层区间入栈。

快速排序的非递归实现代码示例如下，可以结合分析理解：

// 单独封装快速排序的核心部分
int PartSort1(int* a, int left, int right)// 快速排序hoare版本
{int keyi = left;int begin = left, end = right;while (begin < end){// 右边找小while (begin < end && a[end] >= a[keyi]) end--;// 左边找大while (begin < end && a[begin] <= a[keyi]) begin++;Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin;// key被交换到begin处，begin为新的keyi，返回
}
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{// 栈模拟实现非递归ST st;STInit(&st);// STInit是栈初始化// 区间入栈STPush(&st, right);// STPush是入栈STPush(&st, left);while (!STEmpty(&st))// 栈为空则所有区间排序完毕，结束排序{// 前面是先入right后入left，取就要先取left再取rightint left = STTop(&st);// STTop是取栈顶元素STPop(&st);// STPop是出栈int right = STTop(&st);STPop(&st);// 区间取完就可以从栈中删除// 对区间[left,right]进行一趟快排，并将新的keyi存储下来int keyi = PartSort1(a, left, right);// 下一层区间拆分为：[left, keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){// 先入右STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi - 1){// 再入左STPush(&st, keyi - 1);STPush(&st, left);}// 下一层的左右区间入栈就继续下一次循环，继续对后面区间排序}STDestroy(&st);// 排序结束，销毁栈
}

2.6 归并排序

2.6.1 归并排序（递归实现）

归并排序的核心思想是：对于两个有序数组，依次比较它们最小的数，并将最小数放到临时数组，完成一趟排序后再放回原数组。

例如某数组有6个元素1 3 5 2 4 6，我们可以将其对半分成A、B两个部分，A1 3 5与B2 4 6。
我们依次比较它们最小的数，1和2比较，1更小于是将1放到临时数组tmp中；2再与A中剩下的数的最小值比较，也就是3与2比较，2更小，于是将2放到tmp中；接着是3与4比较，3更小于是放到tmp中；接着5与4比较，4更小于是放到tmp中；接着5与6比较，5更小于是放到tmp中；此时A已经遍历完了，而B中还剩下数据未比较完，但B内数据都是有序的，因此我们直接将B中剩下的所有数据依次放进tmp即可。最终tmp中依次存储了数据1 2 3 4 5 6，一趟归并排序完成，将tmp中的数据拷贝回原数组。

那如何将这种思想应用到任意数组上呢？其实直接插入排序里我们已经得到答案了，那就是递归到小区间。因为单个数据一定是有序的，所以我们可以先将数组不断拆分，一直拆分到数组被划分成若干个只有两个数的区间，这时任一区间对半分成A、B两部分，那A、B不就分别只有一个元素了吗？A、B不就都是有序区间了。我们再按归并的思想将两个数的小区间排序好，那我们就可以排四个数的区间，四个数的区间排好，我们就可以排更大的区间。

有人可能问，如果遇到元素个数为奇数等无法对半分的情况怎么办？其实很简单，A、B部分不一定要个数相等，更重要的是A、B部分内是有序的。即使其中一个只有一个元素，而另一个有一万个元素，我们也只需要不断比较最小值，直到其中一个数组遍历完，再将剩余数据放进临时数组。

之所以追求对半分，是因为效率以及空间占用的问题。在前面快排的递归调用中我们已经接触过这种情况，如果区间按对半分的话，归并排序的时间复杂度和快排一样是O(N*logN)，而空间复杂度则由于临时数组的问题是O(N)。

归并排序递归实现代码示例如下：

// 归并排序
// 时间复杂度：O(N*logN) 空间复杂度：O(N)
void _MergeSort(int* a, int* tmp, int left, int right)
{if (left == right) return;// 判断无效区间int mid = (left + right) / 2;// 取中间元素_MergeSort(a, tmp, left, mid);// 先排左区间，使左区间有序_MergeSort(a, tmp, mid + 1, right);// 再排右区间，使右区间有序// 左右区间都有序，开始归并int begin1 = left, end1 = mid;// 记录A部分首尾区间int begin2 = mid + 1, end2 = right;// 记录B部分首尾区间int i = left;// i负责记录tmp数组中已存入的元素while (begin1 <= end1 && begin2 <= end2)// 遍历A、B{// 取小的放到tmp中if (a[begin1] >= a[begin2]) tmp[i++] = a[begin2++];else tmp[i++] = a[begin1++];}// 清空剩余未排完数据的区间while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}// 归并结束，拷贝tmp中数据回原数组memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)// 递归实现
{int* tmp = (int*)malloc(sizeof(int) * n);// 创建临时数组if (!tmp)// 判断是否成功申请空间{perror("MergeSort::malloc fail!");return;}_MergeSort(a, tmp, 0, n - 1);// 调用归并排序算法free(tmp);// 排序结束释放临时空间
}

2.6.2 归并排序（非递归实现）

如何用非递归的方式实现归并排序呢？还是用栈或者队列吗？并不需要，我们有更简单的方式。
其实我们可以发现，对于归并而言，它的区间变化是有明显逻辑的。
归并排序往往从大小为n的区间，一直拆分到大小为2的区间，然后对大小为2的区间排序，所有区间大小为2的区间排序完就可以对区间大小为4的区间排序，排完又可以对更大区间排序。
因此我们可以模拟希尔排序，设置一个gap值。代码示例如下：

void MergeSortNonR(int* a, int n)// 非递归实现
{// 创建临时数组int* tmp = (int*)malloc(sizeof(int) * n);if (!tmp){perror("MergeSort::malloc fail!");return;}// gap=1意味着排序区间的A、B部分的大小初始为1// 实际还是从大小为2的区间开始归并（A、B合起来）// gap>=n意味着A、B其中之一没有元素，归并即可结束int gap = 1;// 用gap控制归并排序的整体流程，每趟归并结束gap*=2表示可以归并的区间不断扩大while (gap < n){// 遍历数组对各个区间进行归并// 每次都从i=0开始，到i<n即遍历完数组结束// 每次for循环从i+=2*gap开始，因为数组被拆分成若干个区间{a[0],a[1],a[2]...}// 以gap=1为例，i=0可以找到a[0]a[1]区间，i+=2*gap-->i=2可以找到a[2]a[3]区间// 以此类推for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// 区间是按2倍来扩张，可能存在无效区间，因此需要判断// 区间的A部分[begin1, end1]B部分[begin2, end2]// 情况1：end1 >= n；情况2：begin2 >= n；此时B部分都无效将A部分放入tmp即可// 情况3：end2 >= n；此时B部分存在有效区间，将end2置为最大下标n-1即可if (begin2 >= n) break;if (end2 >= n) end2 = n - 1;int j = i;// j记录tmp数组中的存储情况while (begin1 <= end1 && begin2 <= end2){// 取小的放到tmp中if (a[begin1] >= a[begin2]) tmp[j++] = a[begin2++];else tmp[j++] = a[begin1++];}// 清空剩余未排完数据的区间while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}// 一趟归并排序结束，拷贝tmp中数据到原数组// 需要注意拷贝的是tmp[i]与其后的数据到a[i]与其后// 拷贝个数是end2-i+1memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);
}

2.7 计数排序

计数排序作为非比较排序是怎么排的呢？
这其实牵涉到了”极差“。对于任意数组，例如数组1 10 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11，这段数据的极差为11-1=10。极差求的是一组数据中最大值与最小值的差值。求这个有什么用呢？

仍以数组1 10 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11为例，我们可以根据极差建立一个临时数组count[11]，接着遍历数组，数组中有11个1，1再减去数组的最小值得到0，我们令count[0] = 11，也就是将数据减去最小值的差值当作它的序号，将数据的个数当作数据存储在count中。

count最终数据存储情况如下count[0]=11 count[1]=1 count[2]=1 count[3]=1 count[4]=1 count[5]=1 count[6]=1 count[7]=1 count[8]=1 count[9]=2 count[10]=1。

数组中最小值为1，count[0]=11代表与最小值差为0的数有11个，也就是有11个1；count[2]=1 count[3]=1 count[4]=1都是指与最小值差为2/3/4的有1个，也就是分别有1个3，4，5；count[9]=2是指与最小值差为9的有2个，也就是有2个10。

于是我们可以直接遍历count数组进行排序。
先读count[0]=11，于是我们在原数组的a[0]到a[10]都存入一个最小值+0——1；再读count[1]=1，于是我们在原数组的a[11]存入一个最小值+1——2；以此类推，对于count[9]=2就在数组中存入两个最小值+9——10。
最终原数组就完成了排序，变成1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 10 11。

计数排序代码示例如下：

// 计数排序——只适合整数，数据范围集中，可排负数
// 时间复杂度：O(N + range) 空间复杂度：O(range)
// range是极差
void CountSort(int* a, int n)
{// 找该组数据中的最大值与最小值，求极差int max = a[0], min = a[0];for (int i = 1; i < n; i++){if (a[i] > max) max = a[i];if (a[i] < min) min = a[i];}int range = max - min + 1;// 申请计数的数组count// 申请range * sizeof(int)个字节的空间，并将所有字节初始化为0int* count = (int*)calloc(range, sizeof(int));//int* count = (int*)malloc(range * sizeof(int));//memset(count, 0, sizeof(int) * range);// 或malloc申请，用memset进行初始化if (!count){perror("CountSort::calloc fail!");return;}// 计数for (int i = 0; i < n; i++) count[a[i] - min]++;// 排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--) a[j++] = i + min;}free(count);
}

三、算法的复杂度与稳定性分析

最后拓展一个稳定性的概念，在某些情况下，我们需要特别关注排序的稳定性，例如比较结构体时。
通常一个结构体有多个可比较的变量。

// 定义一个 学生 结构体变量
struct student
{int age;// 年龄int score;// 成绩int weight;// 体重int height;// 身高
}

当我们要排序一个结构体变量时，我们需要以年龄优先，从大到小，如果年龄相同，则按成绩排序。这时当我们按年龄排完序，我们就不希望按成绩排序时改变年龄顺序了，因此排序的稳定性就十分重要了。

稳定性定义如下：假定在待排序的序列中，存在多个相同的元素，若经过排序，这些元素的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

这是网上找的一个排序算法的复杂度与稳定性表，其中希尔排序的时间复杂度记住大致在O(N^1.3)即可。
重点是稳定性分析：
直接插入排序是稳定的。直接插入排序是先将a[0]看作有序区间，拿有序区间后的a[1]依次与有序区间比较，只有遇见小于它的有序区间元素才插入进去，其后有序区间不断扩大，遍历数组依次比较即可完成排序。这个过程是稳定的。

希尔排序是不稳定的。原因很简单，预排序就导致它一定不稳定，因为预排序是跳着挑选元素进行插入排序的，因此可能挑选到相同元素中靠后的那个，然后交换到前面去。

选择排序是不稳定的。我们记住一种情况即可，即数组6 6 1 1，我们从左边开始遍历数组找最小值，我们找到了第3个元素1，1就被交换到了左端，本来在前面的左端的6被交换到了后面，这就改变了顺序。

堆排序是不稳定的。假设有一任意数组，例如5 5 5 5 5 8，我们需要经过建堆与排序两步完成堆排。建堆并不会改变数组顺序，因为它是符合堆结构的。但排序就会先将最后一个元素与堆顶元素交换，也就是8交换到了第一个5的位置，然后再对8进行向下调整，这就改变了相同元素的原始顺序。

冒泡排序是稳定的。冒泡是将较大值依次交换到后面，相等数据是不会管的，因此是稳定的。

快速排序是不稳定的。因为不管是霍尔法还是前后指针法还是挖坑法，都涉及了交换，交换就容易导致不稳定，因为本来在后面的小值可能被R找到，结果被L交换到前面去了。

归并排序是稳定的。因为归并是对两个有序区间取小值放进临时数组中。对于相同元素的比较，我们可以设计只取前半部分，因此归并可以稳定。

计数排序是稳定的。如何保证计数排序的稳定性呢？介绍一个简单粗暴的方法，仍以结构体变量为例，我们可以遍历原数组，从前往后依次查找对应元素，这就能保证计数排序一定稳定。

---