文章目录
排序的基础知识
1. 排序的概念
什么是排序：所谓排序，就是使一串记录按照其中的某个或某些关键字的大小，按递增或递减方式排列起来的操作。
排序的稳定性：假定在待排序的记录序列中存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为该排序算法是不稳定的。
为什么要关注排序的稳定性：
在知道排序稳定性的概念之后，很多同学可能都会产生一个疑问：我们为什么要注重排序算法的稳定性呢？这里我以高考成绩排名的例子来阐述。
我们知道，由于高考人数众多，出现几个人或者几十个人成绩相同的情况是完全有可能的，那么对成绩相同的同学我们如何进行排名呢？答案是按科目成绩科目进行排名。
假设我们规定，当高考成绩相同时，语文成绩高者排前面；那么我们在对高考成绩进行排名时，就可以先按所有考生的语文成绩进行一次排序，将语文成绩高的排在前面，然后再按总成绩进行一次排序，得出最终排名，那么这里就对排序的稳定性提出要求了，如果我们使用的排序算法不稳定，那么成绩总相同的两个人的排名就可能出现错误。当然，这里只是拿高考排名举例，具体高考成绩怎么排名我们不用关心。
所以，在特殊场景下，对排序的稳定性是有要求的；另外，排序的稳定性在校招中也被经常考查。
内部排序：数据元素全部放在内存中的排序；我们的插入排序、选择排序以及交换排序都是内部排序。
外部排序：由于待排序的记录太多，不能同时放入内存中，而是需要将待排序的记录存储在外存中，待排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换；这种排序方法就称为外部排序；我们的归并排序既可以用于内部排序，也可以用于外部排序。
比较排序：通过比较两个元素的大小来确定元素在内存中的次序，我们常见的入选择排序、插入排序、比较排序与归并排序都属于比较排序。
非比较排序：通过确定每个元素之前，应该有多少个元素来排序，常见的非比较排序有基数排序、计数排序与桶排序。
2. 常见排序分类
生活中常见的排序算法可以分为以下五类：
3. 排序的运用
排序在我们的日常生活中是非常常见的，比如我们在京东/淘宝上购物商品时，可以选择按销量排序、按价格排序、按评论排序，又比如世界500强企业，中国前50所高校等等，这些地方都需要用到排序。
常见排序算法的实现
注：本文章所有的排序算法都以升序为例。
1. 直接插入排序
1.1 排序思想
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就运用了插入排序的思想：
动图演示
如图：当我们插入第 i (i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
1.2 代码实现
// 直接插入排序voidInsertSort(int* a,int n){for(int i =0; i < n -1; i++){int end = i;int tmp = a[end +1];//记录最后一个元素//当目标元素为最小元素，end为-1时退出循环while(end >=0){//如果大于tmp中的数据，就往后挪并--endif(a[end]> tmp){
a[end +1]= a[end];
end--;}//如果小于等于tmp中的数据，就跳出循环准备插入else{break;}}//将数据插入到end的后一个位置
a[end +1]= tmp;}}
注意事项
1、对于单趟排序来说，假设该趟数组共有 m 个数据，我们认为前 m-1 个数据是有序的，我们只需要将最后一个数据插入并且仍然保存数组有序即可；
2、比较过程中需要挪动数据，这里我们从数组倒数第二个元素开始比较，如果该元素大于目标元素就把数组往后移动一位，最后当 a[end] <= tmp 时，该位置的后一个位置 (前面空出来的位置) 就是目标元素的位置；
3、在上面的代码中，由于我们让 end = i ，tmp = a[end+1]，即 tmp 保存的是最后一个元素的下一个元素，所以 for 循环的循环变量 i 应该小于 n-1；
4、当 tmp 中的元素小于数组中的任意元素时，为了避免数组越界，while循环的 end 应该大于等于0，此情况下退出循环时 end = -1，tmp 被放入 a[0]，程序正常。
1.3 复杂度及稳定性
时间复杂度
最坏情况：当待排序的数组为逆序时，我们第一次插入需要挪动1个数据，第二次插入需要挪动2个数据，… … 第n次插入需要挪动n-1个数据，所以需要挪动的次数是一个等差数列，时间复杂度为 O(N^2)；
最好情况：当待排序的数组为顺序时，每一次插入都不需要挪动数据，时间复杂度为 O(N)；
所以直接插入排序的时间复杂度为：**O(N^2)**。
空间复杂度
直接插入排序没有额外的空间消耗，空间复杂度为：O(1)。
稳定性
直接插入排序每次选出数组中最小的数据，同时，当 a[j] = a[i] 时，min 并不会被重新赋值为 a[j]，而是只有当 a[j] < a[i] 时才会改变 min，所以排序前后相同大小的 a[i] 和 a[j] 的相对位置并不会改变，稳定。
1.4 特性总结
- 元素集合越接近有序，直接插入排序算法的时间效率越高；
- 时间复杂度：O(N^2)；
- 空间复杂度：O(1)；
- 稳定性：稳定
2. 希尔排序
2.1 排序思想
希尔排序法又称缩小增量法，也是插入排序的一种，是对直接插入排序的优化。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成 gap 个组，所有距离为 gap 的记录分在同一组内，并对每一组内的记录进行直接插入排序，然后重复上述分组和排序的工作，当全部分组都进行排序后，最后再整体进行一次直接插入排序，使得文件内所有记录达到有序。
画图演示
2.2 代码实现
// 希尔排序 -- 版本1（三层循环）//void ShellSort(int* a, int n)//{// int gap = n;// //gap>1时代表预排序，gap==1时代表直接插入排序// while (gap > 1)// {// gap = gap / 3 + 1;// //对所有组数据进行排序// for (int i = 0; i < gap; i++)// {// //对一组数据进行插入排序// for (int j = i; j < n - gap; j += gap)// {// int end = j;// int tmp = a[end + gap];// while (end >= 0)// {// if (a[end] > tmp)// {// a[end + gap] = a[end];// end -= gap;// }// else// {// break;// }// }// a[end + gap] = tmp;// }// }// }//}// 希尔排序 -- 版本2（两层循环）voidShellSort(int* a,int n){int gap = n;//gap>1时代表预排序，gap==1时代表直接插入排序while(gap >1){
gap = gap /3+1;//i++：i每次加1，而不是加gap，表示对所有组进行并排(所有组同时进行插入排序)for(int i =0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while(end >=0){if(a[end]> tmp){
a[end + gap]= a[end];
end -= gap;}else{break;}}
a[end + gap]= tmp;}}}
注意事项
1、关于 gap 的取值：我们知道，gap 越大，大的数据就能越快的到后面去，小的数据能越快的到前面来，但数据的有序性较低；gap 越小，大的数据到后面和小的数据到前面和后面的速度较慢，但是数据的有序性就越高；所以综合二者考虑，为了提高效率，大佬Knuth提出了 gap 随数据个数和排序次数变化的思路，即 gap 最开始对于元素个数 n，之后每预排一组数据，gap 就减小2倍或者3倍 (这里采取的是每次减小3倍)；
2、对于版本1来说，我们每次只排序一组数据，当这一组排完之后再排序下一组数据，所以我们需要用两层 for 循环嵌套来保证每一组数据都被排序；但对于版本2来说，我们每次让 i 加1，即让所有组数据同时进行排序 (第一组插入一个元素后让第二组插入一个元素，然后第三组，… …，当所有组都插入一个元素后再插入第一组的下一个元素，… …)，所以只需要使用一个 for 循环。
3、当 gap 等于1时，相当于对整体进行直接插入排序 ；
4、无论 gap = n 为奇数还是偶数，gap 经过不断除3加1后，进行最后一趟排序时 gap 一定等于1 (大家可以带几个值进去试一下)，这也是 gap 每次除3后都加1的目的，此趟排序使得数组全部元素有序。
2.3 复杂度及稳定性
时间复杂度
在希尔排序中，因为 gap 的取值方法不唯一，导致其时间复杂度很难去计算，因此在一些优秀的数据结构书籍中给出的希尔排序的时间复杂度也都不固定：
因为我们的 gap 是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照蓝色框的时间复杂度来算，可以大概记忆为：**O(N1.3)**；
空间复杂度
希尔排序没有额外的内存消耗，空间复杂度为：**O(1)**；
稳定性
和直接插入排序不同，希尔排序是不稳定的：因为在预排序过程中，数值相同的元素可能会被分配到不同组中，不同组进行插入排序之后，数值相同的元素的相对位置就可能会发生改变，所以不稳定。
2.4 特性总结
- 希尔排序是对直接插入排序的优化；
- 当 gap > 1时都是预排序，目的是让数组更接近于有序；当gap == 1时，数组已经接近有序的了，这使得最后一次的插入排序效率很高，从而达到整体效率优化的效果；
- 时间复杂度：O(N1.3) (不准确)；
- 空间复杂度：O(1)；
- 稳定性：不稳定
3. 直接选择排序
3.1 排序思想
直接选择排序即每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序数据元素排完；这里我们对其做一些简单的优化 – 每次选两个数，选出最小的放在最前面，选出最大的放在最后面。
动图演示 (未优化)
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，然后在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
3.2 代码实现
// 交换两个数据voidSwap(int* e1,int* e2){int tmp =*e1;*e1 =*e2;*e2 = tmp;}// 直接选择排序voidSelectSort(int* a,int n){int begin =0;int end = n -1;while(begin < end){//一次选两个数，把最小的放前面，最大的放后面int mini = begin, maxi = begin;for(int i = begin +1; i <= end; i++){if(a[i]< a[mini])
mini = i;if(a[i]> a[maxi])
maxi = i;}Swap(&a[begin],&a[mini]);//当最大的数在最前面时，我们需要修正maxi，放在其被覆盖if(maxi == begin)
maxi = mini;Swap(&a[end],&a[maxi]);//迭代
begin++;
end--;}}
注意事项
优化后的直接选择排序存在一个隐藏的 bug：当最大的数位于数组最前面 (maxi == begin) 时，a[begin] 和 a[mini] 交换后会使得最大数 a[begin] 被移动到 mini 下标处，此时我们需要修正 maxi，使得程序能够选出最大的数。
3.3 复杂度及稳定性
时间复杂度
不同于插入排序，对于直接选择排序来说，数据有序或者无序并不会改变排序的效率，因为它始终是通过遍历比较数组元素来求得最大值或者最小值，时间复杂度：**O(N^2)**；
空间复杂度
直接选择排序没有额外的内存消耗，空间复杂度为：**O(1)**；
稳定性
直接选择排序给我们的直观感受是稳定的，因为它每次选择元素时，只有当遇到比自己小的元素时才更新 mini，与自己相等的元素并不会更新 mini，所以相等元素间的相对位置不会发生改变，但其实它是不稳定的；
我们以 8 9 85 5 为例，我们第一次排序发现 5 为最小元素，所以 mini = 3，然后交换 a[0] 与 a[mini]，第一次排序之后的数组为：5 9 8 8 5，大家仔细对比第一次排序前和排序后的数组，发现了什么问题？没错，8 和 8 之间的相对位置发生了改变，所以说直接选择排序其实是不稳定的。（注：这里为了方便理解，我们以未优化的直接选择排序为例）
3.4 特性总结
- 直接选择排序思想非常好理解，但是效率不好，实际中很少使用；
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
4. 堆排序
4.1 排序思想
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种；它通过堆来进行选择数据；需要注意的是排升序要建大堆，排降序建小堆。
4.2 排序实现
关于堆排序我前面单独写了文章来介绍，具体细节请移步至：【数据结构】堆的应用 – 堆排序和TopK问题
4.3 复杂度与稳定性
时间复杂度
堆排序建堆的时间复杂度为 O(N)，选数的时间复杂度为 O(NlogN)，所以堆排序的时间复杂度为：**O(NlogN)**；
空间复杂度
堆排序直接在原数组上进行建堆和选数操作，没有额外的内存消耗，空间复杂度为：**O(1)**；
稳定性
由于堆排序中相同的数据做父节点还是孩子节点，做左孩子还是做右孩子，这些都没有规定，所以堆排序也是不稳定的。
4.4 特性总结
- 相比于直接选择排序，堆排序使用堆来选数，效率提高了很多；
- 时间复杂度：O(N*logN)；
- 空间复杂度：O(1)；
- 稳定性：不稳定；
5. 冒泡排序
5.1 排序思想
交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序的基本思想：冒泡排序是交换排序中一种简单的排序方法，它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，最终达到有序的目的。
由于冒泡排序本身并不知道待排序的数据是否是有序的，所以即便目标数据已经有序，它还是会继续进行比较，知道循环达到循环截止条件；所以为了提高效率，我们可以对冒泡排序进行简单的优化 – 增加一个有序判断，使得当目标数据有序时冒泡排序能够跳出循环，停止排序。
动图演示
5.2 代码实现
// 冒泡排序voidBubbleSort(int* a,int n){int i =0;int j =0;for(i =0; i < n -1; i++){int exchange =0;for(j =0; j < n - i -1; j++){if(a[j]> a[j +1]){Swap(&a[j],&a[j +1]);
exchange =1;}}if(exchange ==0)//如果数组已经有序，则直接跳出循环，不再排序break;}}
5.3 复杂度及稳定性
时间复杂度
最坏情况：数据是逆序的，第一趟排序要交换n-1个数据，第二趟要交换n-2个数据… …，最后一趟要交换1个数据，所以交换的次数合计也是一个等差数列，时间复杂度为 O(N^2)；
最好情况：对于未优化的冒泡排序来说，数据是否有序并不会影响排序的效率，时间复杂度都为 O(N^2)；但对于优化后的冒泡排序来说，当数据是有序的情况下，其时间复杂度可以达到 O(N)；
所以时间复杂度：O(N^2)；
空间复杂度
冒泡排序没有额外的内存消耗，空间复杂度为：**O(1)**；
稳定性
冒泡排序每趟排序过程中，只有当前一个元素大于后一个元素时才会发生交换，当二者相等时并不会发生交换，所以相等元素间的相对位置不会发生改变，稳定。
5.4 特性总结
- 冒泡排序是一种非常容易简单且理解的排序；
- 时间复杂度：O(N^2)；
- 空间复杂度：O(1)；
- 稳定性：稳定；
6. 快速排序 (重点)
6.1 排序思想
快速排序是 Hoare 于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
6.2 快排递归版本
在了解快排的思想之后，我们会发现快速排序的排序过程是这样的：先选定一个 key 做基准值，经过单趟排序后 key 左边位置的元素都小于 key，右边位置的元素都大于 key，这就使得 key 的位置被最终确定，即我们一趟排序可以确定一个元素的位置；现在我们只需要对 key 的左区间和右区间再进行单趟排序即可；key 的左区间经过单趟排序之后又会确定一个元素的位置，然后再对该元素的左右区间进行单趟排序，直到 key 的左右区间只有一个元素 (一个元素本身就有序，不需要再进行排序) 或者不存在左右区间时说明排序完成。
经过上面的分析我们发现，快排的排序过程和二叉树的前序遍历十分相似，我们每趟排序可以确定一个元素的位置，然后我们就只需要排序该位置的左右区间即可，左右区间又可以被划分为左右区间，即不断被划分为子问题，这就是递归的思想。
// 快速排序递归实现voidQuickSort(int* a,int left,int right){//如果左右区间相等或者右区间小于左区间直接返回if(right <= left)return;//单趟排序 -- 确定单个元素的位置int keyi =PartSort1(a, left, right);//递归左区间QuickSort(a, left, keyi -1);//递归右区间QuickSort(a, keyi +1, right);}
关于快排的单趟排序，现在主流的主要有三种方法：hoare 法、挖坑法以及前后指针法，下面我们依次介绍。
注：快排所有代码中的 keyi 代表的都是数组的下标，key 则是代表数组中的元素。
6.3 hoare 法
hoare 法的算法思想是这样的：我们取最左边的元素做 key，然后定义两个指针 – L 和 R，L 指向区间第一个元素，R 指向区间最后一个元素，然后让 R 先走，当 R 遇到小于等于 key 的元素时就停下来，然后让 L 走，L 遇到大于等于 key 的数时停下来，之后让 L 和 R 所对应的值进行交换；最后重复上面的步骤，直到 L 和 R 相遇；二者相遇位置所对应的值一定是小于 key 的，这时候再交换 key 和 L/R 即可。
代码实现
// 快速排序hoare版本intPartSort1(int* a,int left,int right){int keyi = left;//取最左边的元素做keywhile(left < right){//右先走，找小//left<right：避免left和right错过或者越界//=：避免死循环while(left < right && a[right]>= a[keyi]){
right--;}//左后走，找大while(left < right && a[left]<= a[keyi]){
left++;}Swap(&a[left],&a[right]);}//记录二者相遇的位置并让其与key交换int meet = left;Swap(&a[meet],&a[keyi]);return meet;}
注意事项
1、我们需要保存的是数组元素的下标 keyi，而不是具体的元素 key，因为在 partsort 函数中，key 只是形参，而形参的改变不会影响数组元素 a[left]；
2、在写循环条件时，我们需要加上 left < right，这是为了避免当 keyi 右边的元素全部大于 a[keyi] 时，R 不会停止而造成数组越界；同时也避免 L 在往右走的过程中直接越过 R，不会在相遇点停止；
3、另外，当等于 a[keyi] 时，L 和 R 也不要做停留，避免出现 a[keyi] == a[left] == a[right] 这种情况从而导致程序死循环。
这里还有一个问题：为什么 L 和 R 相遇位置对应的元素一定小于 key？关键在于让 R 先走；具体分析如下：
我们知道，L 和 R 相遇只可能是两种情况：L 撞 R，或者 R 撞 L；
当 L 撞 R 时，由于 R 是先走的，所以 R 下标对应的元素一定是小于 key 的，结论成立；
当 R 撞 L 时，又分为两种情况：1、L 一直没动，此时 L == R == keyi，交换后不变；2、L 动过，而 L 动过后，R 在动之前一定是 L 和 R 之间发生了交换，所以此时 L 下标对应的值也大于 key，结论也成立。
排序优化
经过上面的努力我们已经成功实现了快速排序，但是我们可以对其中的两个逻辑进行优化：一是选 key 逻辑，二是递归小区间。
优化选 key 逻辑
我们知道，当前我们是选择区间的第一个位置作为 keyi，然后通过单趟排序确定该元素的位置，那么最好的情况就是我们每次取出的 keyi 对应的值都是该区间的中位数，这样我们就能不断二分，效率非常高。
那么最坏的情况就应该是当数组有序或者接近的时候，在这种情况下我们可以认为 key 就处于最左边，这样每次递归左区间长度为0，右区间长度为 n-1，那么递归的深度就为 n，即一共要建立 n 层栈帧，但是我们知道，栈区的空间是非常小的，只有8M左右，那么当数据量较大，比如10W、100W的时候就会发生栈溢出，导致程序崩溃。
针对数组有序或相对有序造成程序栈溢出的情况，有人对选 key 的逻辑提出了以下三种优化方法：
1、随机选数 – 这样使得每次 key 都为最小值的概率变得很小；
2、选中间下标做 key – 专门针对有序进行优化；
3、三数取中 – 取 left、right、mid 三个下标对应数值的中间值做 key。
这里我们采用第三种优化方法：
//三值取中intGetMidIndex(int* a,int left,int right){int mid = left +(right - left)/2;//防止溢出//找出三个下标对应数值中居中的一个int max1 = a[left]> a[mid]? a[left]: a[mid];int max2 = a[mid]> a[right]? a[mid]: a[right];int min = max1 < max2 ? max1 : max2;//返回居中值对应的下标if(min == a[left])return left;elseif(min == a[mid])return mid;elsereturn right;}
优化后的单趟排序代码
// 快速排序hoare版本intPartSort1(int* a,int left,int right){//三值取中做keyint mid =GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int keyi = left;while(left < right){//右先走，找小//left<right：避免left和right错过或者越界//>=：避免死循环while(left < right && a[right]>= a[keyi]){
right--;}//左后走，找大while(left < right && a[left]<= a[keyi]){
left++;}Swap(&a[left],&a[right]);}//记录二者相遇的位置并让其与key交换int meet = left;Swap(&a[meet],&a[keyi]);return meet;}
递归小区间优化
我们知道，在完全二叉树中，最后一层的节点数占总结点数的 1/2，倒数第二次的节点数占总结点数的 1/4，倒数第三层占1/8，也就是说，完全二叉树最后三层的递归调用次数占总递归调用次数的 87.5%；
对于快排来说，虽然我们递归下来的树不是完全二叉树 (不是每一次的 key 都为中位数)，但是大体上是差不多的；而且快排递归还有一个特点，那就是递归下来最后几层的元素很少 (倒数第三层为8个数左右，倒数第二次为4个数左右，倒数第一层为2个数左右)，并且它们都是较为有序的，所以当区间长度小于等于8时我们可以直接使用直接插入排序，而不是让其继续递归分割子区间，从而达到提高效率的目的。
优化后的递归函数
// 快速排序递归实现 -- 递归优化voidQuickSort(int* a,int left,int right){//如果左右区间相等或者右区间小于左区间直接返回if(right <= left)return;//当递归到元素个数小于等于8的区间时，为了提高效率直接使用插入排序if((right - left)+1<=8)// right-left+1 得到区间元素个数{InsertSort(a + left, right - left +1);//+1易错}else{int keyi =PartSort1(a, left, right);//递归左区间QuickSort(a, left, keyi -1);//递归右区间QuickSort(a, keyi +1, right);}}
6.4 挖坑法
挖坑法的算法思想如下：
首先，我们利用三数取中筛选出适合数值，然后让其与最左边的元素进行交换，再让 key = a[left]；其次，定义两个变量 L 和 R，分别指向区间开始和区间末尾，与 hoare 法不同的是，挖坑法会多增加一个变量 hole，用来记录坑的位置，同时，hoare 中使用的是 keyi (数组下标），而挖坑法中使用的是 key (下标对应的元素)；
如下图：坑最开始的位置在最左边，我们让 R 先走，当 R 找到比 key 小的值之后与 a[hole] 进行交换，并让 R 的位置作为新的坑；然后让 L 走，找比 key 大的位置，找到后也与坑所在位置的元素进行交换并更新坑；最后重复上述过程，直到 L 与 R 相遇，此时直接用 key 覆盖掉 L/R/hole (代表同一个位置) 对应位置的元素即可。
代码实现
// 快速排序挖坑法intPartSort2(int* a,int left,int right){//三值取中做keyint mid =GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int key = a[left];int hole = left;while(left < right){//右边找小while(left < right && a[right]>= key){
right--;}//填坑并形成新坑
a[hole]= a[right];
hole = right;//左边找大while(left < right && a[left]<= key){
left++;}//填坑并形成新坑
a[hole]= a[left];
hole = left;}
a[hole]= key;return hole;}
6.5 前后指针法
前后指针法的算法思想如下：
首先，最开始还是和前面两种方法一样，利用三数取中函数来优化选 key 的逻辑，但是后面的步骤就有较大的区别了；我们定义三个变量：keyi = left、prev = left 和 cur = left+1，其中的 keyi 代表 key 值所在的下标，而 prev 和 cur 就是我们的主角 – 前后指针了；
我们让 cur 先走，当找到小于 a[keyi] 的元素时停下来，然后先让 prev++，再判断 prev 是否等于 cur，如果不等于就交换二者对应元素的值，然后重复前面的步骤，直到 cur > right；最后交换 a[keyi] 和 a[prev] 即可
代码实现
// 快速排序前后指针法intPartSort3(int* a,int left,int right){//三值取中作keyint mid =GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int keyi = left;int prev = left, cur = left +1;while(cur <= right){//cur找小if(a[cur]< a[keyi]){
prev++;if(prev < cur)//如果prev和cur位置不重叠，就交换Swap(&a[prev],&a[cur]);}
cur++;}Swap(&a[keyi],&a[prev]);return prev;}
注意事项
1、因为 prev 是从 keyi 的位置开始的，而 keyi 在循环结束时才进行交换，所以我们需要先让 prev++，再观察 prev 是否等于 cur，如果相等也没有交换的必要了；
2、如果不相等，由于 cur 比 prev 先走，并且 cur 只有遇到小于 a[keyi] 的值才停下来，所以 a[prev] 一定大于 a[keyi]，二者进行交换；
3、当 cur > right 跳出循环后，prev 并没有再次进行自增，那么 a[prev] 一定是小于 a[keyi] 的，所以直接交换二者即可。
6.6 快排递归版本完整代码
以 hoare法 为例：
// 交换两个数据voidSwap(int* e1,int* e2){int tmp =*e1;*e1 =*e2;*e2 = tmp;}//三值取中intGetMidIndex(int* a,int left,int right){int mid = left +(right - left)/2;//防止溢出//找出三个下标对应数值中居中的一个int max1 = a[left]> a[mid]? a[left]: a[mid];int max2 = a[mid]> a[right]? a[mid]: a[right];int min = max1 < max2 ? max1 : max2;//返回居中值对应的下标if(min == a[left])return left;elseif(min == a[mid])return mid;elsereturn right;}// 快速排序hoare版本intPartSort1(int* a,int left,int right){//三值取中做keyint mid =GetMidIndex(a, left, right);Swap(&a[left],&a[mid]);int keyi = left;while(left < right){//右先走，找小//left<right：避免left和right错过或者越界//>=：避免死循环while(left < right && a[right]>= a[keyi]){
right--;}//左后走，找大while(left < right && a[left]<= a[keyi]){
left++;}Swap(&a[left],&a[right]);}//记录二者相遇的位置并让其与key交换int meet = left;Swap(&a[meet],&a[keyi]);return meet;}// 快速排序递归实现 -- 递归小区间优化voidQuickSort(int* a,int left,int right){//如果左右区间相等或者右区间小于左区间直接返回if(right <= left)return;//当递归到元素个数小于等于8的区间时，为了提高效率直接使用插入排序if((right - left)+1<=8)// right-left+1 得到区间元素个数{InsertSort(a + left, right - left +1);//+1易错}else{int keyi =PartSort3(a, left, right);//递归左区间QuickSort(a, left, keyi -1);//递归右区间QuickSort(a, keyi +1, right);}}
6.7 快排非递归版本
经过上面的学习，我们已经知道如何使用递归的方式来实现快速排序，但是大家仔细思考会发现，上面递归的过程其实是数组区间变化的过程 (先是整个数组，然后是左右区间，左右区间又被划分为左右区间)，而数组的区间可以用 left 和 right 边界来表示；这样，我们快排非递归的思路就出来了；
快排非递归需要借助另外一个数据结构 – 栈：首先我们将数组的左右边界 (左闭右闭) 入栈，然后取出栈顶的 right 和 left (取出元素的同时进行 pop)，此时，我们就可以用 left 和 right 来代表一个区间了；之后，我们调用单趟排序函数对此区间进行排序；排序完成后再将此区间的左右区间进行入栈操作；最后重复上述步骤，直到栈为空即可。
另外，我们为什么要去研究快排的非递归呢？首先，对于未优化的快排，当数据元素有序或者接近有序时递归深度为N，而递归调用函数的栈帧是在栈区上开辟的，而栈区本身很小，只有8M左右，所以当数据量较大的时候我们需要将递归改为非递归（即循环）来避免栈溢出；其次，对于优化后的快排来说，三数取中只能保证我们每次选出的 key 值不是最小或者次小的数，那么这里就存在一种可能 – 我们每次选出的 key 为倒数第三、第四小的，在这种情况下如果我们的数据量非常大，比如几亿，那么也是有可能发生栈溢出的，所以说在某些极端场景下优化后的快排也是需要使用非递归的。
代码实现
// 快速排序 非递归实现voidQuickSortNonR(int* a,int left,int right){
ST st;StackInit(&st);//入区间StackPush(&st, left);StackPush(&st, right);while(!StackEmpty(&st)){//出区间int right =StackTop(&st);StackPop(&st);int left =StackTop(&st);StackPop(&st);//单趟排序int keyi =PartSort1(a, left, right);//如果区间元素大于1，就入区间//先入右区间if(right > keyi +1){StackPush(&st, keyi +1);StackPush(&st, right);}//再入左区间if(keyi -1> left){StackPush(&st, left);StackPush(&st, keyi -1);}}StackDestory(&st);}
注意事项
1、由于这里我们使用了数据结构中的栈，所以我们需要将我们之前完成的 Stack.h 和 Stack.c 添加到当前项目中来，并且在 Sort.c 中包含 Stack.h；
2、由于栈是后入先出的，所以如果我们入栈的顺序是 left right 的话，出栈的顺序就只能是 right left；
3、这里我为了模拟递归调用的过程，所以在单趟排序之后选择先入右区间，再入左区间 (这样使得左区间先出栈，先进行单趟排序，和递归顺序相同)，大家也可以先入左区间，再入右区间；
6.8 复杂度及稳定性
时间复杂度
递归版本：快排递归的深度大约是 logN，每一层的元素个数大约是 N，所以时间复杂度为：**O(NlogN)**；
非递归版本：非递归和递归情况类似，入栈出栈的时间复杂度为 O(N)，然后左右子区间差不多可以划分 logN 次，所以时间复杂度为：**O(NlogN)**；
空间复杂度
递归版本没有额外的空间消耗，空间复杂度为：**O(1)；非递归版本的栈有额外空间消耗，空间复杂度为：O(logN)**；
稳定性
由于快速排序选出的 key 值是不确定的，所以不稳定；
6.9 特性总结
- 快速排序整体的综合性能和使用场景都是比较好的，所以被称之为快速排序；
- 时间复杂度：O(N*logN)；
- 空间复杂度：O(1) – 递归，O(logN) – 非递归；
- 稳定性：不稳定；
7. 归并排序 (重点)
7.1 排序思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
动图演示
7.2 归并排序递归版本
如上图所示：如果说快速排序递归实现相当于二叉树的前序遍历的话，那么归并排序的递归实现就可以认为是二叉树的后序遍历；因为归并思想实质上就是将两个有序数组排成一个有序数组，其实我们前面学习顺序表链表的时候做的合并两个有序数组 以及合并两个有序链表 运用的就是归并思想；
所以，对于归并其实我们并不陌生，归并的实现也十分简单，就是不断取小的元素尾插；困难的是如何达到归并的条件 – 被归并的两个区间里面的元素必须是有序的；这时候我们就需要用到递归的思想了，我们需要不断将待排序的区间分为左右两个子区间进行递归，直到左右子区间区间的大小为1，然后再进行归并 (只有一个元素的区间必定是有序的)；归并之后返回至上一层，待上一层的右区间变成有序后归并上一层，然后再返回上一层的上一层，直到第一层有序；大家可以与二叉树后序遍历中的先访问左子树，再访问右子树，最后访问根节点结合起来理解。
具体案例如下：下图中经过归并后的 6 10、1 7、3 9、2 4实际上是会返回至上一层覆盖掉原来的 10 6、7 1、3 9、4 2的，后面的 1 6 7 10、2 3 4 9，以及最后的 1 2 3 4 6 7 9 10也是一样，图中只是形象的画法。
代码实现
void_MergeSort(int* a,int left,int right,int* tmp){//当区间大小为1时，无左右区间，直接返回if(left >= right)return;int mid = left +(right - left)/2;//递归左区间有序_MergeSort(a, left, mid, tmp);//递归右区间有序_MergeSort(a, mid +1, right, tmp);//当左右区间都有序时开始归并 -- 取小的尾插int left1 = left, right1 = mid;//左区间int left2 = mid +1, right2 = right;//右区间//在tmp数组中的相应位置尾插int i = left;while(left1 <= right1 && left2 <= right2){if(a[left1]<= a[left2]){
tmp[i++]= a[left1++];}else{
tmp[i++]= a[left2++];}}//将较大的数组链接到tmp后面while(left1 <= right1){
tmp[i++]= a[left1++];}while(left2 <= right2){
tmp[i++]= a[left2++];}//将tmp中已归并的数据拷贝到原数组的相应区间上memcpy(a + left, tmp + left,sizeof(int)*(right - left +1));}// 归并排序递归实现voidMergeSort(int* a,int n){//开辟一个额外数组用于归并int* tmp =(int*)malloc(sizeof(int)* n);if(tmp ==NULL){perror("malloc fail\n");exit(-1);}//归并排序_MergeSort(a,0, n -1, tmp);//销毁free(tmp);
tmp =NULL;}
注意事项
1、与合并两个有序数组不同，合并两个有序数组中它 nums1 给定的大小是 m+n，即两个数组和的大小，所以我们可以直接将归并后的数据放入到 nums1 中进行返回；但是在这里，待合并的两个有序区间中没有剩余的空间来存放另一个区间中的元素，所以我们需要单独开辟一个与输入数组等大的 tmp 数组来保存两个区间归并后的结果。
2、在每一次归并完成之后，我们都需要将 tmp 中归并的结果拷贝到原数组中，这里需要特别注意的是我们进行拷贝的区间，因为 tmp 中保存的是整个数组区间中一部分小区间归并后的结果，所以我们拷贝的时候也应该拷贝到原数组的对应区间中。
7.3 归并排序非递归版本
与快排的递归不同，归并排序的左右区间是严格进行二分的，即归并排序递归下来是一颗完全二叉树，所以递归的深度为 logN，那么归并排序的递归自然就不存在栈溢出的问题，毕竟当数据量为10亿的时候，递归的深度也才30，也就是说，归并排序非递归的价值其实不大；但是，由于归并排序非递归版本涉及到的边界问题非常复杂，有的公司会用它来考察我们的编程能力，基于这个原因，我们还是来学习一下它。
归并排序的非递归不能使用栈来实现，因为同一区间的 left 或 rihgt 可能会别多次使用，而是像斐波那契数列一样，通过前面的区间来得到后面的区间；
如上图，我们定义一个 gap 变量，用于指定每次进行排序的一组数据元素的个数，然后定义循环，让两组数据进行归并，待数组所有组都两两归并之后，我们再让 gap *= 2，让其归并更大组的数据，直到 gap > n 时，数组有序；
但是上述方法只能用于排序拥有 2^n 个数据的数组，当数组元素个数不满足这个条件时，就会发生越界访问：
可能发生的越界情况一共有三种：
1、第一组越界：第一组越界时只可能是 right 越界，因为如果连第一组的 left 都越界了那根本就不会进行归并，此时，第二组一定全部越界；这种情况下只有一组数据，不需要归并，直接break；
2、第二组全部越界，即第二组 left 越界，第一组没越界；这种情况下也只有一组数据，不需要归并，直接break
3、第二组部分越界，即第二组的 right 越界，left 没越界；此时存在两组数据，需要将第二组的right修正，然后继续进行归并；
代码实现
// 归并排序非递归实现voidMergeSortNonR(int* a,int n){int* tmp =(int*)malloc(sizeof(int)* n);if(tmp ==NULL){perror("malloc fail\n");exit(-1);}//gap从1开始，每次gap个与gap个数据进行归并排序int gap =1;while(gap < n){for(int j =0; j < n; j +=2* gap){//gap为每一组包含的数据个数int left1 = j, right1 = j + gap -1;//第一组int left2 = j + gap, right2 = j +2* gap -1;//第二组//当存在以下三种情况时，会发生数组越界，需要我们进行特殊处理//1、当第一组部分越界时，第二组一定越界，此时只有一组数据，不需要归并，直接breakif(right1 >= n)break;//2、当第二组全部越界时，也只有一组数据，不需要归并，直接breakif(left2 >= n)break;//3、当第二组部分越界时，此时存在两组数据，需要将第二组的right修正，继续归并if(right2 >= n)
right2 = n -1;//归并排序//在tmp数组中的相应位置尾插int i = j;while(left1 <= right1 && left2 <= right2){if(a[left1]<= a[left2]){
tmp[i++]= a[left1++];}else{
tmp[i++]= a[left2++];}}//将较大的数组链接到tmp后面while(left1 <= right1){
tmp[i++]= a[left1++];}while(left2 <= right2){
tmp[i++]= a[left2++];}//归并两组数据就拷贝两组数据，而不是最后整体拷贝//整体拷贝可能会因为越界break时没有进行归并造成随机值覆盖memcpy(a + j, tmp + j,sizeof(int)*(right2 - j +1));}//每次gap增加二倍
gap *=2;}free(tmp);
tmp =NULL;}
7.4 复杂度及稳定性
时间复杂度
对于递归版本的归并排序来说，递归的深度为 logN，每一层待排序的元素个数都为 N，所以时间复杂度是严格的 O(NlogN)；对于非递归来说，gap 每次增加二倍，每次 gap 中待排序的数据等于或者小于 N，所以非递归的时间复杂度也是 O(NlogN)；
空间复杂度
归并排序需要额外开辟一个与原数组同等大小的数组用于归并，所以空间复杂度为：O(N)；
稳定性
归并排序的稳定性取决于我们单次归并过程中是取较小的元素尾插，还是取较小和相等的元素尾插，我们上面实现的归并排序是稳定的。
不稳定：
while(left1 <= right1 && left2 <= right2){if(a[left1]< a[left2]){
tmp[i++]= a[left1++];}else{
tmp[i++]= a[left2++];}}
稳定：
while(left1 <= right1 && left2 <= right2){if(a[left1]<= a[left2]){
tmp[i++]= a[left1++];}else{
tmp[i++]= a[left2++];}}
7.5 排序特性
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题；
- 时间复杂度：O(NlogN)；
- 空间复杂度：O(N)；
- 稳定性：稳定。
8. 计数排序
8.1 排序思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，属于非比较排序；其实就是将数组中对应数据出现的次数，映射到一个新的已初始化的数组的对应的下标中，每出现一次，下标对应的值就自增一次；而映射又分为绝对映射和相对映射，相对映射是对绝对映射的优化。
绝对映射
力扣中的 找到所有数组中消失的数字 其实就是绝对映射的一个经典题目，其实现实际上很简单 – 我们先遍历一遍原数组，找出原数组中的最大元素，然后开辟一个比原数组大1的新数组，接着我们将原数组映射到新数组中，最后我们遍历新数组，根据新数组中对应下标中值输出即可。
相对映射
在学习了绝对映射后，我们发现绝对映射存在两个缺陷：
- 当数据值很大时时，空间消耗过大；比如我们要对数组 a = { 5001, 4989, 5010, 4550} 进行计数排序，我们需要开辟一个大小为 5011 的新数组；
- 绝对映射不能排序负数，因为数组下标不可能为负数。
基于绝对映射存在的这些缺陷，我们设计出了相对映射来对其进行一定程度上的优化；绝对映射的基本思路是：
我们不再根据数组的最大元素来开辟空间，而是根据数组中最大元素与最小元素的差值来开辟空间；比如上面的数组 a 中最大元素为5010，最小元素为4550，那么我们就只需要开辟 5010-4550+1 即61个整形的空间；
相应的，我们在进行映射时也不再直接映射元素值到对应的新数组下标中，而是让元素元素值减去最小值之后再进行映射；这样，即使数组元素为负数，那么当其减去最小值之后也会映射到大于0的下标中去；最后，当我们取出元素覆盖原数组时，再让其加上最小值即可。
8.2 代码实现
// 计数排序voidCountSort(int* a,int n){//找出数组中的最大值和最小值，为相对映射做准备int i =0;int min = a[0], max = a[0];for(i =1; i < n; i++){if(a[i]< min)
min = a[i];if(a[i]> max)
max = a[i];}//相对映射区间int range = max - min +1;//左闭右闭区间，元素范围需要+1//因为需要将CountArr中的元素全部初始化为0，所以直接使用calloc函数int* CountArr =(int*)calloc(range,sizeof(int));if(CountArr ==NULL){perror("malloc fail\n");exit(-1);}//相对映射：将数组a中对应数据出现的次数映射到CountArr数组中对应的下标中，出现几次，下标对应的值就++几次for(i =0; i < n; i++){
CountArr[a[i]- min]++;//减去min的作用：1、相对映射，节省空间 2、可以排序负数}//排序int j =0;for(i =0; i < range; i++){while(CountArr[i]--){
a[j++]= i + min;//加上min：数据复原}}//销毁free(CountArr);
CountArr =NULL;}
8.3 计数排序的缺陷
计数排序虽然看起来效率很高，但是它有如下两个缺陷：
- 只能排序整形数据，不能排序浮点数、字符串等其他类型的数据；
- 只使用与数据分布范围较小的情景，当数据分布较分散时，空间消耗太大；
8.4 特性总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(N+range)；
- 空间复杂度：O(range)；
9. 排序总结
排序方法平均情况最好情况最坏情况辅助空间稳定性直接插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(nlogn)~O(n²)O(n1.3)O(n²)O(1)不稳定直接选择排序O(n²)O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定冒泡排序O(n²)O(n)O(n²)O(1)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)~O(n)不稳定归并排序O(nlogn)O(nlogn)O(n*logn)O(n)稳定
排序性能测试函数
// 测试排序的性能对比voidTestOP(){srand((unsignedint)time(NULL));constint N =100000;int* a1 =(int*)malloc(sizeof(int)* N);int* a2 =(int*)malloc(sizeof(int)* N);int* a3 =(int*)malloc(sizeof(int)* N);int* a4 =(int*)malloc(sizeof(int)* N);int* a5 =(int*)malloc(sizeof(int)* N);int* a6 =(int*)malloc(sizeof(int)* N);if(a1 ==NULL){perror("malloc fail");return;}for(int i =0; i < N;++i){
a1[i]=rand();
a2[i]= a1[i];
a3[i]= a1[i];
a4[i]= a1[i];
a5[i]= a1[i];
a6[i]= a1[i];}int begin1 =clock();//InsertSort(a1, N);int end1 =clock();int begin2 =clock();//ShellSort(a2, N);int end2 =clock();int begin3 =clock();//SelectSort(a3, N);int end3 =clock();int begin4 =clock();//HeapSort(a4, N);int end4 =clock();int begin5 =clock();QuickSortNonR(a5,0, N -1);int end5 =clock();int begin6 =clock();//MergeSort(a6, N);int end6 =clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);}
八大排序完整项目代码：Sort/Sort · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
版权归原作者 野猪佩奇` 所有， 如有侵权，请联系我们删除。