一.排序的基础知识
1.排序的概念
什么是排序：所谓排序，就是使一串记录按照其中的某个或某些关键字的大小，按递增或递减方式排列起来的操作。
排序的稳定性：假定在待排序的记录序列中存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为该排序算法是不稳定的。
为什么要关注排序的稳定性：
在知道排序稳定性的概念之后，很多同学可能都会产生一个疑问：我们为什么要注重排序算法的稳定性呢？这里我以高考成绩排名的例子来阐述。
我们知道，由于高考人数众多，出现几个人或者几十个人成绩相同的情况是完全有可能的，那么对成绩相同的同学我们如何进行排名呢？答案是按科目成绩科目进行排名。
假设我们规定，当高考成绩相同时，语文成绩高者排前面；那么我们在对高考成绩进行排名时，就可以先按所有考生的语文成绩进行一次排序，将语文成绩高的排在前面，然后再按总成绩进行一次排序，得出最终排名，那么这里就对排序的稳定性提出要求了，如果我们使用的排序算法不稳定，那么成绩总相同的两个人的排名就可能出现错误。
所以，在特殊场景下，对排序的稳定性是有要求的；另外，排序的稳定性在校招中也被经常考查。
内部排序：数据元素全部放在内存中的排序；我们的插入排序、选择排序以及交换排序都是内部排序。
外部排序：由于待排序的记录太多，不能同时放入内存中，而是需要将待排序的记录存储在外存中，待排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间地交换；这种排序方法就称为外部排序；我们的归并排序既可以用于内部排序，也可以用于外部排序。
比较排序：通过比较两个元素的大小来确定元素在内存中的次序，我们常见的选择排序、插入排序、比较排序与归并排序都属于比较排序。
非比较排序：通过确定每个元素之前，应该有多少个元素来排序，常见的非比较排序有基数排序、计数排序与桶排序。
转载自【数据结构】八大经典排序（两万字大总结）
2.常见算法排序概览
3.排序的应用
排序在我们的日常生活中是非常常见的，比如我们在京东上购物商品时，可以选择按销量排序、价格排序、评论排序，又比如世界500强企业，中国前100所高校等等，这些地方都需要用到排序。
二.八大排序介绍
1.直接插入排序
- 基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际中我们玩扑克牌时，就运用了插入排序的思想：
动图演示：
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
- 过程分析：
插入排序，听名字就觉着是有一串数字，随后插入了1个数字，并将其排成有序，是这样吗？当然不是，但是抽象来看确实有点道理。
- 假如我们已经有一串有序的数组【2，3，5，8，10】，现在想再插入一个数字7使其仍然有序，该如何比呢？
实现过程很简单，只需要拿数组依次从后往前跟插入的数字比较，如果插入的数字比原有序数字最后一个的值小，那把最后一个数字往后挪，此时会出现一个空位，当挪到插入的数字放到空位刚好有序时停止，如下图示：
- 但是上述情况仅支持其是有序的情况下，如果原本给出的一串数字是无序呢？如何利用插入排序？如下列一串乱序数字：
- 9 1 2 5 7 4 8 6 3 5
解法很简单，既然给定的一串数字是无需的，那就把第一个数字看成有序并用变量tmp将其保存起来，把第二个数字看成是插入进去的数字进行挪动排序覆盖像上文一样，排好了前两个数字，再把第三个数字看成是插入进去的数字进行挪动排序覆盖，此时前三个数字就有序了，依次类推，最终数字均是有序的。
- 动图演示：
现在再来看直接插入排序似乎也没这么难，也就是把原数字的从第1个数字开始就看作有序，每次把后面的数字看成要插入的，然后进行排序，随后以此类推，继续看作有序，继续插入……直至数字全部插入进去。
- 代码实现：
//直接插入排序 void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { //单趟排序 int end = i; int tmp = a[end + 1]; //将tmp视为插入的数字 while (end >= 0) { if (tmp < a[end]) //若插入的数字小于有序数字的最后一个数 { a[end + 1] = a[end]; //将大于tmp的值往后挪 --end; } else { break; } } 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个数据，第二次插入需要挪动2个数据，…… 第n次插入需要挪动n-1个数据，所以需要挪动的次数是一个等差数列，时间复杂度为 O(N2)；
最好情况：当待排序的数组为顺序时，每一次插入都不需要挪动数据，时间复杂度为 O(N)；
所以直接插入排序的时间复杂度为：O(N2)。
空间复杂度：直接插入排序没有额外的空间消耗，空间复杂度为：O(1)。
稳定性：直接插入排序每次选出数组中最小的数据，同时，当 a[j] = a[i] 时，min 并不会被重新赋值为 a[j]，而是只有当 a[j] < a[i] 时才会改变 min，所以排序前后相同大小的 a[i] 和 a[j] 的相对位置并不会改变，稳定。
直接插入排序特性总结
1、元素集合越接近有序，直接插入排序算法的时间效率越高
2、时间复杂度：O(N2)
3、空间复杂度：O(1)
4、稳定性：稳定
2.希尔排序
- 基本思想：
希尔排序其实是建立在直接插入排序的基础上进行的优化，希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
而上述操作可以分为两大部分：
- 预排序：间隔为gap得数据分为一组
- 直接插入排序
假如有这样一串乱序数组：
- 9 1 2 5 7 4 8 6 3 5
希尔排序的预排序就是让大的数尽快到后面去，小的数尽快到前面去，以此接近有序。而预排序利用的又是分组排。比如说它给出的间隔gap为3，那么上述中，【9，5，8，5】这4个数就分为一组，【1，7，6】这3个数分为一组，【2，4，3】分为一组。总的来说：gap为几，这里就会分割成几组数据。分组后如下图：
接下来分别对每一组进行插入排序的思想对这gap组数据进行排序。
既然是分组进行插入排序，那就好办了，像第一组：【9，5，8，5】排序后为【5，5，8，9】，第二组【1，7，6】排序后为【1，6，7】，第三组【2，4，3】排序后为【2，3，4】，如图所示：
- 动图演示其过程：
- 代码演示预排序：
void ShellSort(int* a, int n) { int gap = 3; for (int j = 0; j < gap; j++) { //控制gap组都进行预排序 for (int i = j; i < n - gap; i += gap) { //确保一组中的数据都进行插入排序 int end = i; //定义一个变量tmp保存end的后一个数,其下标是end+gap int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end];//如果end下标的数值大于后面的值tmp，也就意味着end下标的值要往后挪 end -= gap; } else { break; } } //单趟循环结束或循环中直接break出来均直接赋值 a[end + gap] = tmp; } } }这里可以看出第一次预排成功，达到想要的效果了，但是此段代码我们套了三层循环，可以对它进行优化
- 多组并列预排序：
只需要把第二层的for循环中的i+=gap变化为i++即可，i+=gap再和第一层循环结合的目的是，每一组进行排序，排好了进入下一组。而现在省去第一趟循环，把第二趟的条件改为i++，恰好实现了多组并列进行预排序。
- 动图演示：
- 代码如下：
//希尔排序 void ShellSort(int* a, int n) { int gap = 3; //控制gap组都进行预排序 for (int i = 0; i < n - gap; i++) { //确保一组中的数据都进行插入排序 int end = i; //定义一个变量tmp保存end的后一个数,其下标是end+gap int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end];//如果end下标的数值大于后面的值tmp，也就意味着end下标的值要往后挪 end -= gap; } else { break; } } //单趟循环结束或循环中直接break出来均直接赋值 a[end + gap] = tmp; } }
- 注意：
- gap为1，它就是直接插入排序
- 如果gap越小，数据跳的越慢，但是数据越接近有序
- 如果gap越大，大的数据可以越快跳到后面，小的数据可以越快跳到前面，但是数据越不接近有序
现在我们面临一个问题：gap到底取值多少？
如果gap给小了，并且数组情况最坏是逆序且数组很长，那么大的数想要到后面就要跳很多次，预排序效率太低，那么还用希尔排序干啥呢？直接用插入排序或者冒泡排序，反正效率都差不多。如果gap给大了，大的数据就能越快的到后面去，小的数据能越快的到前面来，但数据的有序性较低。综上，我们可以再套一层循环，此循环不光接近gap的问题，还实现了多次预排直至排序结束达到最终效果。
//1、gap > 1 预排序 //2、gap == 1 直接插入排序 int gap = n; while (gap > 1) { gap = gap / 3 + 1; //+1能够保证最后一次gap一定是1 //…… 预排序 }这里我们可以看到这样一个循环，实现了多组预排序直至最终效果，我们控制gap要分类，当gap > 1就继续预排序，当gap == 1就插入排序，而 gap = gap / 3 + 1足矣满足上述要求，或者说gap=n/2，gap/=2;这行代码也可以实现。仔细体会这行代码。
- 总代码如下：
//希尔排序 void ShellSort(int* a, int n) { //1、gap > 1 预排序 //2、gap == 1 直接插入排序 int gap = n; while (gap > 1) { gap = gap / 3 + 1; //+1能够保证最后一次gap一定是1 //控制gap组都进行预排序 for (int i = 0; i < n - gap; i++) { //确保一组中的数据都进行插入排序 int end = i; //定义一个变量tmp保存end的后一个数,其下标是end+gap int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end];//如果end下标的数值大于后面的值tmp，也就意味着end下标的值要往后挪 end -= gap; } else { break; } } //单趟循环结束或循环中直接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的目的，此趟排序使得数组全部元素有序。
- 时间复杂度：在希尔排序中，因为 gap 的取值方法不唯一，导致其时间复杂度很难去计算，因此在一些优秀的数据结构书籍中给出的希尔排序的时间复杂度也都不固定。
因为我们的 gap 是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照蓝色框的时间复杂度来算，可以大概估算为：O(N1.3)；
空间复杂度：希尔排序没有额外的空间消耗，空间复杂度为：O(1)。
稳定性：和直接插入排序不同，希尔排序是不稳定的：因为在预排序过程中，数值相同的元素可能会被分配到不同组中，不同组进行插入排序之后，数值相同的元素的相对位置就可能会发生改变，所以不稳定。
希尔排序特性总结
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3.时间复杂度分析：
希尔排序的时间复杂度不是很好算，我们先简要看下预排序的时间复杂度：
- gap很大时，数据跳的很快，里面套的循环可以忽略不记，差不多是O(N)。
- gap很小时，数据跳的很慢，很接近有序，差不多也是O(N)
再来看外面套上循环后的时间复杂度：
while循环中的gap = gap / 3 + 1相当于是循环了log3N次
既然外循环执行log3N次，内循环执行N次，那么时间复杂度为O(N * log3N)。但是上述计算顶多是估算，Knuth在大量的实验基础上推出其时间复杂度应为：O(N1.3)
4.空间复杂度: O(1)
5.稳定性：不稳定
3.选择排序
- 动图演示：
- 基本思想：
遍历一遍数组选出最小的放在前面，剩下的数再遍历一遍，再选出小的放前面，以此类推直至遍历完毕排序结束。如下的一串数组：
虽说是遍历一遍，选出最小的数放在最前面，但并不是覆盖到最前面，而是进行交换。比如说我遍历了一遍，最小为1，跟第一个9交换，再从剩下的选出最小的2放到第二个位置……
- 这里我们做出一点改动进行优化：
遍历一次，选出两个数，最小的和最大的，最小的放到第一个位置，最大的放到最后一个位置，随后缩小区间，在这个区间内重复上述操作。
- 画图演示：
- 代码演示：
//选择排序 void SelectSort(int* a, int n) { int left = 0; int right = n - 1; while (left < right) { int mini = left, maxi = left; for (int i = left + 1; i <= right; i++) { if (a[i] < a[mini]) { mini = i; //遍历一遍数组，选出最小的下标 } if (a[i] > a[maxi]) { maxi = i; //遍历一遍数组，选出最大的下标 } } //排升序。大值放右边，小值放左边 Swap(&a[left], &a[mini]); //如果left和maxi重叠，修正下maxi即可 if (left == maxi) { maxi = mini; } Swap(&a[right], &a[maxi]); //交换完后，缩小区间 left++; right--; } }
注意事项：优化后的直接选择排序存在一个隐藏的 bug：当最大的数位于数组最前面 (maxi == begin) 时，a[begin] 和 a[mini] 交换后会使得最大数 a[begin] 被移动到 mini 下标处，此时我们需要修正 maxi，使得程序能够选出最大的数。
时间复杂度：不同于插入排序，对于直接选择排序来说，数据有序或者无序并不会改变排序的效率，因为它始终是通过遍历比较数组元素来求得最大值或者最小值，时间复杂度：O(N2)；
空间复杂度：直接选择排序没有额外的内存消耗，空间复杂度为：O(1)；
稳定性：
直接选择排序给我们的直观感受是稳定的，因为它每次选择元素时，只有当遇到比自己小的元素时才更新 mini，与自己相等的元素并不会更新 mini，所以相等元素间的相对位置不会发生改变，但其实它是不稳定的；
我们以 8 9 8 5 5 为例，我们第一次排序发现 5 为最小元素，所以 mini = 3，然后交换 a[0] 与 a[mini]，第一次排序之后的数组为：5 9 8 8 5，大家仔细对比第一次排序前和排序后的数组，发现了什么问题？没错，8 和 8 之间的相对位置发生了改变，所以说直接选择排序其实是不稳定的。（注：这里为了方便理解，我们以未优化的直接选择排序为例）
选择排序特性总结
1、直接选择排序思考非常好理解，但是效率不是很好,实际中很少使用
2、时间复杂度：O(N2)
3、空间复杂度：O(1)
4、稳定性：不稳定
4.堆排序
堆排序我在上篇博文已经重点讲解过，这里简要提下
- 对数组建堆要向下调整建堆，因为其时间复杂度小
- 排升序要建大堆，排降序建小堆
如若各位小伙伴们还有些疑问，可以看这一下这篇博客：
- 这里直接给出代码：
//堆排序 void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整 -- 大堆 void AdjustUp(int a[], int child) { int parent = (child - 1) / 2; //找出父节点 while (child > 0) //当调整到根节点时不再调整 { if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); } else { break; } //迭代 child = parent; parent = (child - 1) / 2; } } //向下调整 -- 大堆 void AdjustDown(int* a, int n, int parent) { int minChild = parent * 2 + 1; while (minChild < n) { // 找出小的那个孩子 if (minChild + 1 < n && a[minChild + 1] > a[minChild]) { minChild++; } if (a[minChild] > a[parent]) { Swap(&a[minChild], &a[parent]); parent = minChild; minChild = parent * 2 + 1; } else { break; } } } // O(N*logN) 堆排序 void HeapSort(int* a, int n) { // 大思路：选择排序，依次选数，从后往前排 // 升序 -- 大堆 // 降序 -- 小堆 //建堆 -- 向上调整建堆：O(N*logN) //for (int i = 1; i < n; i++) //{ // AdjustUp(a, i); //} // 建堆 -- 向下调整建堆: O(N) for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } //排序 -- 升序（建大堆，向下调整）：O(N*logN) for (int i = n - 1; i > 0; i--) { Swap(&a[i], &a[0]); //交换堆尾和堆顶的元素 AdjustDown(a, i, 0); //向下调整 } /*int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); ++i; }*/ }注意事项：
时间复杂度：堆排序建堆的时间复杂度为 O(N)，选数的时间复杂度为 O(N*logN)，所以堆排序的时间复杂度为：O(N*logN)；
空间复杂度：堆排序直接在原数组上进行建堆和选数操作，没有额外的内存消耗，空间复杂度为：O(1)；
稳定性：由于堆排序中相同的数据做父节点还是孩子节点，做左孩子还是做右孩子，这些都没有规定，所以堆排序也是不稳定的。
堆排序特性总结
1、堆排序使用堆来选数，效率就高了很多。
2、时间复杂度：O(N*logN)
3、空间复杂度：O(1)
4、稳定性：不稳定
5.冒泡排序
- 基本思想：
冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：它重复地走访过要排序的元素列，依次比较两个相邻的元素如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。
- 排序步骤：
- 相邻的两个元素比较，大的上浮，小的下沉，这样一趟冒泡排序即可确保大值排列在一端
- 确定趟数，趟数为数组总个数-先前排过的趟数
- 动图演示：
- 代码如下：
//交换 void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } //冒泡排序 void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { //单趟 for (int i = 1; i < n - j; i++) { if (a[i - 1] > a[i]) { Swap(&a[i], &a[i - 1]); } } } }
- 冒泡排序的优化：
根据上述代码，有个缺陷：如果我的数组本身就有序或着说是接近有序，那我还需要每一趟都进去比较相邻两个数字的大小吗？如果每次都要比，那时间复杂度就要提升，为此可以定义一个变量exchange，如果说发生了比较，那么exchange的值保存为1，如果没有比较，则exchange为0，就退出
- 总代码如下：
//交换 void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } //冒泡排序优化 void BubbleSort(int* a, int n) { for (int j = 0; j < n; j++) { int exchange = 0; //单趟 for (int i = 1; i < n - j; i++) { if (a[i - 1] > a[i]) { exchange = 1; Swap(&a[i], &a[i - 1]); } if (exchange == 0) { break; } } } }
稳定性：
冒泡排序每趟排序过程中，只有当前一个元素大于后一个元素时才会发生交换，当二者相等时并不会发生交换，所以相等元素间的相对位置不会发生改变，稳定。
冒泡排序特性总结
1、冒泡排序是一种非常容易理解的排序
2、稳定性：稳定
3、空间复杂度：O(1)
4、时间复杂度：O(N2)
最好情况：数组本身是顺序的，外层循环遍历一次就完成O(N)
最坏情况：数组本身是逆序的，内外层遍历O(N2)
6.快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序分为三种方法
- hoare法
- 挖坑法
- 前后指针法
而且可以使用递归和非递归来实现，可以说是相当重要的知识，接下来我们依次讲解：
6.1.hoare法
单趟动图演示：
hoare法的快排分为以下步骤：
- 选出一个key，一般是第一个数，或者是最后一个数
- 定义变量L和R，L从左走，R从右走
- R先向前走，找到比key小的位置停下，再让L向后走，找到比key大的值停下
- 交换L和R代表的数值
- 继续遍历，同样让R先走，L后走，同上规则
- 当L和R相遇的时候，把相遇位置的值与key位置的值交换，结束
排完一趟要求结果如下：
- 左边的值都比key小
- 右边的值都比key大
注意事项：
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] 这种情况从而导致程序死循环。
提问：如何保证相遇位置的值比key小？
- 答案：不需要保证，此算法思想（右边先走）可以完美解决。注意看本算法思想，它明确了每次让R先走，R找到比key小的值之后才会停下来，这时候才轮到L走，L要么找不到比key大的值就一直走直至相遇R，此时正好满足小于key，要么L找到比key大，交换L和R的值，但随后，R又会继续向前走，一直走，最坏刚好遇到L，因为L先前和R已经换过一次，也就是说这个L的值一定是比key小的，那么同样交换key的值，综上，此算法思想可以解决。
提问：如若key为最右边的值呢？排完一趟如何？
思想和上面一样，唯一要改变的是此时是L先走，R后走，其余没有变
- 动图演示：
- 接下来，就先写下单趟排序：
//快排单趟排序 int PartSort1(int* a, int left, int right) { int keyi = left; //选左边作keyi while (left < right) { //右边先走，找小 while (left < right && a[right] >= a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left<right { right--; } //右边找到后，左边再走，找大 while (left < right && a[left] <= a[keyi]) //同上，也要加上left<right { left++; } //右边找到小，左边找到大，就交换 if(left < right) Swap(&a[left], &a[right]); } //此时left和right相遇，交换与keyi的值 int meeti = left; Swap(a[keyi], &a[left]); return meeti; }
- 写好了单趟排序，就要进行整体排序了
仔细观察上述单趟排序，有没有发现排完后，key已经排到了正确的位置，因为其左边的值均小于key，而右边的值均大于key，此时key的位置就是最终排序好后应该在的位置。那么如果左边有序，右边有序，那么整体就有序了，只需要用到递归+分治的思想即可。
- 画图演示：
- 总代码如下：
//hoare法 //快排单趟排序 int PartSort(int* a, int left, int right) { int keyi = left; //选左边作keyi while (left < right) { //右边先走，找小 while (left < right && a[right] >= a[keyi]) //防止right找不到比keyi小的值直接飙出去，要加上left<right { right--; } //右边找到后，左边再走，找大 while (left < right && a[left] <= a[keyi]) //同上，也要加上left<right { left++; } //右边找到小，左边找到大，就交换 if(left < right) Swap(&a[left], &a[right]); } //此时left和right相遇，交换与keyi的值 int meeti = left; Swap(&a[keyi], &a[left]); return meeti; } //快速排序 void QuickSort(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) { return; } int keyi = PartSort(a, begin, end); //分成左右两段区间递归 // [begin, keyi-1] 和 [keyi+1, end]，中间为keyi QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
6.2.挖坑法
- 动图演示单趟挖坑：
挖坑法的步骤如下：
- 把最左边的位置用key保存起来，此位置形成坑位
- 定义变量L和R分别置于最左和最右
- 让R先向前走，找到比key小的位置停下
- 找到后，将该值放入坑位，自己形成新的坑位
- 再让L向后走，找比key大的位置停下
- 找到后，将该值放入坑位，自己形成新的坑位
- 再让R走……
- 当L和R相遇时，把key的值放到坑位，结束
挖坑法相较于上面的hoare法并没有优化，本质上也没有区别，但是其思想更好理解
- 不需要理解为什么最终相遇位置比key小
- 不需要理解为什么左边做key，右边先走
- 总代码如下：
//挖坑法 int PartSort2(int* a, int left, int right) { //把最左边的值用key保存起来 int key = a[left]; //把left位置设为坑位hole int hole = left; while (left < right) //当left小于right时就继续 { //右边先走，找小于key的值 while (left < right && a[right] >= key) { right--; //如若right的值>=key的值就继续 } //找到小于key的值时就把此位置赋到坑位，并把自己置为新的坑位 a[hole] = a[right]; hole = right; //左边走，找大于key的值 while (left < right && a[left] <= key) { left++; } //找到大于key的值就把此位置赋到坑位，并把自己置为新的坑位 a[hole] = a[left]; hole = left; } //此时L和R相遇，将key赋到坑位 a[hole] = key; return hole; } //快速排序 void QuickSort(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) { return; } int keyi = PartSort2(a, begin, end); //分成左右两段区间递归 // [begin, keyi-1] 和 [keyi+1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
6.3前后指针法
- 动图演示：
前后指针法的步骤如下：
- 把第一个位置的值设为key保存起来
- 定义prev指针指向第一个位置，cur指向prev后一个位置
- 若cur指向的数值小于key，prev和cur均后移
- 当cur指向的数据大于key时，prev不动，cur继续后移
- 当cur的值小于key时，prev后移一位，交换与cur的值，cur再++
- 重复上述操作，当cur越界时，交换此时的prev和key的值。结束
总的来说，cur是在找小，找到后就++prev，prev的值无论怎么走都是小于key的值的，当cur找到大与key时，cur的后面紧挨着的prev是小于key的，接下来让cur++到小于key的值，此过程间prev始终不动，唯有cur找到了小于key的值时，让prev再++，此时的prev就是大于key的值了，仔细揣摩这句话，随后交换cur和prev的值，上述操作相当于是把小于key的值甩在左边，大于key的值甩在右边。
- 总代码如下：
//前后指针法 int PartSort3(int* a, int left, int right) { int key = left;//注意不能写成 int key = a[left] int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[key] && a[++prev] != a[cur]) { Swap(&a[prev], &a[cur]); //在cur的值小于key的值的前提下，并且prev后一个值不等于cur的值时交换， //避免了交换两个小的（虽然也可以，但是没有意义） } cur++; //如若cur的值大于key，则cur++ } Swap(&a[prev], &a[key]); //此时cur越界，直接交换key与prev位置的值 return prev; } //快速排序 void QuickSort(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) { return; } int keyi = PartSort2(a, begin, end); //分成左右两段区间递归 // [begin, keyi-1] 和 [keyi+1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }提问：如若把key设定为最后一个数据呢？该如何控制？
总的来说有三处发生变动：
- cur和prev初始时的位置：先前定义的prev是第一个数据，cur是prev的后一个，而现在，cur是第一个位置，而prev是cur的前一个，相当于是初始时整体后移一位;
- 停止的条件：原先的cur有效范围是整个数组，现在的cur有效范围是前n-1个数组，省去最后一个定为key的值;
- 交换与key的值的条件：先前是cur越界时，直接交换prev与key的值，现在是先++prev，再交换与key的值，（因为此时的prev值依旧小于key，要++后才大于key）。
除了这三处有所变动外，别的没有什么变动，交换的过程步骤都是一样的。
- 动图演示：
- 代码如下：
//前后指针法key在右边 int PartSort3(int* a, int left, int right) { int keyi = right; //变动1： int prev = left - 1; //先前 int prev =left; int cur = left + 1; int cur = left; //变动2： while (cur < right) //先前 while (cur <= right) { if (a[cur] < a[keyi] && a[++prev] != a[cur]) { Swap(&a[prev], &a[cur]); } cur++; } //变动3： Swap(&a[++prev], &a[keyi]); //先前Swap(&a[prev], &a[keyi]); return prev; } //快速排序 void QuickSort(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) { return; } int keyi = PartSort3(a, begin, end); //分成左右两段区间递归 // [begin, keyi-1] 和 [keyi+1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
6.4.快排特性总结
1、快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2、稳定性：不稳定
3、空间复杂度：O(logN)
4、时间复杂度：O(N*logN)
快排的时间复杂度分两种情况讨论：
- 最好：每次选key都是中位数，通俗讲是左边一半右边一半，具体看是key的左序列长度和右序列长度相同。时间复杂度O(N*logN)
- 最坏：每次选出最小的或者最大的作为key。时间复杂度O(N2)
- 画图分析：
可能有人会好奇正常的数组怎么会次次都会选出最小的或者最大的作为key呢？这也太巧合了，但是仔细想想，当数组是有序或者接近有序时，不就是最坏的情况吗？在这种情况下我们可以认为 key 就处于最左边，这样每次递归左区间长度为0，右区间长度为 n-1，那么递归的深度就为 n，即一共要建立 n 层栈帧，但是我们知道，栈区的空间是非常小的，只有8M左右，那么当数据量较大，比如10W、100W的时候就会发生栈溢出，导致程序崩溃。
综上我们需要深思：能否针对快排最坏的情况进行优化？看下文：
6.5.快排优化
就以最坏的情况为例：
假设数组为 【1，2，3，4，5，6，7，8，9，10】
6.5.1.三数取中
针对数组有序或相对有序造成程序栈溢出的情况，有人对选 key 的逻辑提出了以下三种优化方法：
1.随机选数 – 这样使得每次 key 都为最小值的概率变得很小；
2.选中间下标做 key – 专门针对有序进行优化；
3.三数取中 – 取 left、right、mid 三个下标对应数值的中间值做 key。
对于我们自己来说，是很清楚其是有序的，可计算机并不清楚，它依旧是选取最左边或者最右边作为key，如果key不是取最小或者最大的，取出的值是介于之间的，那么情况也会好很多，至此：引出三数取中
- 规则：
取第一个数，最后一个数，中间那个数，在这三个数中选不是最大也不是最小的那个数作为key。此法针对有序瞬间从最坏变成最好，针对随机数，那么选出来的数也同样不是最大也不是最小，同样进行了优化。
三数取中其实针对hoare法，挖坑法，前后指针法都适用，这里我们就以前后指针法示例：
- 总代码如下：
//快速排序 //三数取中优化 int GetMidIndex(int* a, int left, int right) { int mid = (left + right) / 2; // int mid = left + (right - left) / 2 // left mid right if (a[left] < a[mid]) { if (a[mid] < a[right]) // left < mid < right return mid; else if (a[left] < a[right]) // left < right <mid return right; else // right < left < mid return left; } else // left > mid { if (a[right] > a[left]) // right > left > mid return left; else if (a[mid] > a[right])// left > mid > right return mid; else // left > right > mid return right; } } //前后指针法 int PartSort3(int* a, int left, int right) { //三数取中优化 int mid = GetMidIndex(a, left, right); Swap(&a[mid], &a[left]); int keyi = left;//注意不能写成 int key = a[left] int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && a[++prev] != a[cur]) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); return prev; } //快速排序 void QuickSort(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) { return; } int keyi = PartSort3(a, begin, end); //分成左右两段区间递归 // [begin, keyi-1] 和 [keyi+1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); }
6.5.2.小区间优化
假设快排每次递归的过程中，选出key，然后递归分成左边和右边，并且都是均匀的，如果是有序，每次选中间值，这个过程就像是二分，跟二叉树的样子差不多，正如上述画过的图：
快排递归调用的简化图其实就类似于一个二叉树，假设长度N为1000，那么递归调用就要走logN层也就是10层，假设其中一个递归到只有5个数了，那么还要递归3次，当然这只是左边的，右边还要递归3次，这么小的一块区间还要递归这么多次，小区间优化就是为了解决这一问题，针对最后的小区间进行其它的算法排序，就比如插入排序算法就很不错。
当递归到越小的区间时，递归次数就会越多，针对这一小区间采取插入排序更优，减少了大量的递归次数
我们知道，在完全二叉树中，最后一层的节点数占总结点数的 1/2，倒数第二次的节点数占总结点数的 1/4，倒数第三层占1/8，也就是说，完全二叉树最后三层的递归调用次数占总递归调用次数的 87.5%；
对于快排来说，虽然我们递归下来的树不是完全二叉树 (不是每一次的 key 都为中位数)，但是大体上是差不多的；而且快排递归还有一个特点，那就是递归下来最后几层的元素很少 (倒数第三层为8个数左右，倒数第二次为4个数左右，倒数第一层为2个数左右)，并且它们都是较为有序的，所以当区间长度小于等于8时我们可以直接使用直接插入排序，而不是让其继续递归分割子区间，从而达到提高效率的目的。(这个小于多少是不确定的，不过大致有范围)
- 代码如下：
//三数取中 int GetMidIndex(int* a, int left, int right) { int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[right] > a[mid]) return mid; else if (a[right] < a[left]) return left; else return right; } else // a[left] > a[mid] { if (a[mid] > a[right]) return mid; else if (a[right] > a[left]) return left; else return right; } } //前后指针法 int PartSort3(int* a, int left, int right) { //三数取中 int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int prev = left, cur = left + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[cur], &a[prev]); } cur++; } Swap(&a[prev], &a[keyi]); return prev; } //快速排序 void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end - begin <= 8) { InsertSort(a + begin, end - begin + 1); } else { int keyi = PartSort3(a, begin, end); //[begin, keyi-1] keyi [keyi+1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
6.6.快排非递归
先前的学习中，我们的快排都是用递归来实现的，但是要知道：递归也是有缺陷的。如果深度过大，可能会导致栈溢出，即使你用了快排优化可能也无法解决此问题，所以我们引出非递归的版本来解决栈溢出问题。
我们为什么非要去研究快排的非递归呢？首先，对于未优化的快排，当数据元素有序或者接近有序时递归深度为N，而递归调用函数的栈帧是在栈区上开辟的，而栈区本身很小，只有8M左右，所以当数据量较大的时候我们需要将递归改为非递归（即循环）来避免栈溢出；其次，对于优化后的快排来说，三数取中只能保证我们每次选出的 key 值不是最小或者次小的数，那么这里就存在一种可能 – 我们每次选出的 key 为倒数第三、第四小的，在这种情况下如果我们的数据量非常大，比如几亿，那么也是有可能发生栈溢出的，所以说在某些极端场景下优化后的快排也是需要使用非递归的。
- 规则：
在快排递归的过程中是要建立栈帧的，仔细看看每次递归时传的参数，有begin和end，其递归过程存储的是排序过程中要控制的区间，那我们用非递归模拟递归的过程中也要按照它这个存储方式进行，这就需要借助栈了，跟上篇博文的层序遍历一样利用到了栈
依旧以如下乱序数组示例：
- 6 1 2 7 9 3 4 5 10 8
- 代码如下：
//快排非递归 void QuickSortNonR(int* a, int begin, int end) { ST st; StackInit(&st); //先把第一块区间入栈 StackPush(&st, begin); StackPush(&st, end); while (!isStackEmpty(&st)) //栈不为空就继续 { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); //使用前后指针法进行排序 int keyi = PartSort3(a, left, right); // keyi已经到了正确位置 // [left, keyi-1] [keyi+1, right] if (left < keyi - 1)//如若左区间不只一个数就入栈 { StackPush(&st, left); StackPush(&st, keyi - 1); } if (keyi + 1 < right)//若右区间不只一个就入栈 { StackPush(&st, keyi + 1); StackPush(&st, right); } } StackDestory(&st); }上述代码恰好巧妙的实现了递归的过程，仔细观察上述代码，一开始我们入栈了下标为begin和end的值，如下：
随后，取出这两个值，并用right和left分别保存起来，随后对区间[left，right]这块区间进行单趟排序，取出keyi的值为5，此时a[keyi]也就排到了正确的位置了，接下来就是效仿递归的关键了，以keyi为分界线，将数组分为两块区间：【left，keyi-1】和【keyi+1，right】，此时再把这两块区间的入栈：
接下来进入第二趟while循环，同样是再次出栈里的两个数据6和9，并再次传入单趟排序，算出keyi的值为8，也就意味着a[keyi]到了正确的位置，再以keyi为分界线，将右区间的数组分为【6，7】和【9，8】以此类推……一直排下去
注意事项：
1.由于这里我们使用了数据结构中的栈，所以我们需要将我们之前完成的 Stack.h 和 Stack.c 添加到当前项目中来，并且在 Sort.c 中包含 Stack.h；
2.由于栈是后入先出的，所以如果我们入栈的顺序是 left–> right 的话，出栈的顺序就只能是 right–> left；
3.这里我为了模拟递归调用的过程，所以在单趟排序之后选择先入右区间，再入左区间 (这样使得左区间先出栈，先进行单趟排序，和递归顺序相同)，大家也可以先入左区间，再入右区间；
7.归并排序
- 动图演示：
- 基本思想：分治思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
假设我们有左右两块有序区间的数组，可以对它直接进行合并。此时我们需要借助第三方数组，一次比较两块区间的起始位置，把小的那个放到新数组，随后依次比较，小的就放新数组，一直到结束。
但是现在存在一个问题？上述条件是假设了左半区间和右半区间有序，但是原先数组是无序的啊，也就是左半区间和右半区间均无序。怎么才能达到左半区间和右半区间有序最后再归并成整体有序呢？这就体现到了分治的思想了，将数组一直分，分到1个1个的，归并成有序变成2个2个的，然后归并成有序成4个4个的，最后再4个4个的归并成有序，最终至整体有序。
- 画图解析其完整的归并过程：
这里我们先用代码实现其分解递归的过程，并用打印法表示其结果
画图演示其部分递归分治的过程：
- 总代码如下：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; //区间不存在就返回 int mid = (begin + end) / 2; //[begin, mid] [mid+1, end] _MergeSort(a, begin, mid, tmp); //递归左半部分 _MergeSort(a, mid + 1, end, tmp); //递归右半部分 //归并[begin, mid] [mid+1, end] //printf("归并[%d,%d][%d,%d]\n", begin, mid, mid + 1, end); int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { //将较小的值放到tmp数组里头 if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } //如若begin2先走完，把begin1后面的元素拷贝到新数组 while (begin1 <= end1) { tmp[i++] = a[begin1++]; } //如若begin1先走完，把begin2后面的元素拷贝到新数组 while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //归并结束后，把tmp数组拷贝到原数组 memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } //归并排序 void MergeSort(int* a, int n) { //malloc一块新数组 int* tmp = (int*)malloc(sizeof(int) * n); assert(tmp); _MergeSort(a, 0, n - 1, tmp); free(tmp); }
7.1.归并排序非递归
为什么要掌握快排非递归？
与快排的递归不同，归并排序的左右区间是严格进行二分的，即归并排序递归下来是一颗完全二叉树，所以递归的深度为 logN，那么归并排序的递归自然就不存在栈溢出的问题，毕竟当数据量为1亿的时候，递归的深度也才28，也就是说，归并排序非递归的价值其实不大；但是，由于归并排序非递归版本涉及到的边界问题非常复杂，有些老六公司会用它来考察我们的编程能力，基于这个原因，我们还是有必要学习一下它。
思想：
归并的非递归不需要借助栈，直接使用循环即可。递归版中我们是对数组进行划分成最小单位，这里非递归我们直接把它看成最小单位进行归并。我们可以通过控制间距gap来完成，先看图：
上述情况其实是在理想状态下可行的，只要数组长度不是2的次方倍都会出现问题，先简要看下理想状态下的伪代码，并用printf打印下归并过程：
再强调一遍，只要数组长度不是2的次方倍都会出现问题，像上述长度为8没有问题，那如若长度为10呢？
当长度为10不再是2的次方数时就运行出现问题了，综上我们需要考虑下极端情况：根据上述的区间范围，我们可以总结出以下三个可能会出现越界的情况：
- end1越界
- begin2越界
- end2越界
1、end2越界：
2、begin2和end2均越界：
3、end1和begin2和end2均越界
综上，我们需要单独对这些极端情况处理
//end1越界，修正即可 if (end1 >= n) { end1 = n - 1; } //begin2越界，第二个区间不存在 if (begin2 >= n) { begin2 = n; end2 = n - 1; } //begin2 ok，end2越界，修正下end2即可 if (begin2 < n && end2 >= n) { end2 = n - 1; }
- 总代码如下：
//归并非递归 void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(a) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { for (int j = 0; j < n; j += 2 * gap) { int begin1 = j, end1 = j + gap - 1; int begin2 = j + gap, end2 = j + 2 * gap - 1; //end1越界，修正即可 if (end1 >= n) { end1 = n - 1; } //begin2越界，第二个区间不存在 if (begin2 >= n) { begin2 = n; end2 = n - 1; } //begin2 ok，end2越界，修正下end2即可 if (begin2 < n && end2 >= n) { end2 = n - 1; } printf("归并[%d,%d][%d,%d]\n", begin1, end1, begin2, end2); int i = j; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //拷贝回原数组--归并哪部分就拷贝哪部分回去 memcpy(a + j, tmp + j, (end2 - j + 1) * sizeof(int)); } //整体拷贝回原数组 //memcpy(a, tmp, n * sizeof(int)); gap *= 2; } free(tmp); tmp = NULL; }
- 注意事项：
1.与合并两个有序数组不同，合并两个有序数组中它 nums1 给定的大小是 m+n，即两个数组和的大小，所以我们可以直接将归并后的数据放入到 nums1 中进行返回；但是在这里，待合并的两个有序区间中没有剩余的空间来存放另一个区间中的元素，所以我们需要单独开辟一个与输入数组等大的 tmp 数组来保存两个区间归并后的结果。
2.在每一次归并完成之后，我们都需要将 tmp 中归并的结果拷贝到原数组中，这里需要特别注意的是我们进行拷贝的区间，因为 tmp 中保存的是整个数组区间中一部分小区间归并后的结果，所以我们拷贝的时候也应该拷贝到原数组的对应区间中。
- 时间复杂度
对于递归版本的归并排序来说，递归的深度为 logN，每一层待排序的元素个数都为 N，所以时间复杂度是严格的 O(N*logN)；对于非递归来说，gap 每次增加二倍，每次 gap 中待排序的数据等于或者小于 N，所以非递归的时间复杂度也是 O(N *logN)；
- 空间复杂度
归并排序需要额外开辟一个与原数组同等大小的数组用于归并，所以空间复杂度为：O(N)；
- 稳定性
归并排序的稳定性取决于我们单次归并过程中是取较小的元素尾插，还是取较小和相等的元素尾插，我们上面实现的归并排序是稳定的。
7.2.归并排序特性总结
1、归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2、时间复杂度：O(N*logN)
3、空间复杂度：O(N)
4、稳定性：稳定
7.3.内排序和外排序
在排序中，分为内排序和外排序，简单了解下其概念：
- 内排序：数据量较少，在内存中进行排序
- 外排序：数据量很大，在磁盘上进行排序
而我们前面学习的排序中，归并排序既可作为内排序，也可作为外排序，而其它几个排序只能是内排序，这也就说明了在处理数据量很大时，采用归并排序才能解决，其它排序不可。
如若我要排10亿个整数，就只能使用归并排序了，现在来简要算下其占比大小：
- 1G = 1024MB
- 1MB = 1024KB
- 1KB = 1024Byte
- 综上1G = 1024 * 1024 * 1024Byte，而10亿个整数40亿Byte，所以10亿个整数占4G
现在有10亿个整数（4G）的文件，只给你1G的运行内存，请对文件中的10亿个数进行排序
**核心思想：**数据量大，加载不到内存。想办法控制两个有序文件，两个有序文件归并成一个更大的有序文件。可以把这4G的文件分成4等份，每一份1G，分别读到内存进行归并排序，排完后再写回到磁盘小文件。
8.计数排序
- 动图演示：
- 基本思想：
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。用到的是哈希映射的思想。
- 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
假设现在要对如下数组进行排序：
- 10 3 1 4 1 7 3 6
计数的核心步骤就是数组中数字的值是多少，就把该值映射到新开辟数组的下标上。仔细观察这串数组，最大数字为10，所以这里我们要开辟11个空间，才能保证数字10放到新数组下标为10的位置，遍历原数组，一个val出现几次，它映射的位置++几次。
上述方法即哈希的绝对映射思想，原数组的某个元素是多少，对应新开辟数组下标为几的位置就相应的加加，出现几次，加加几次。此方法看似可行，但存在一个大问题，空间复杂度过大，如若一组数据为【10000，9999，5000，6999，7999，8999】，难道说为了排这几个数字，你要开辟10001个大小空间的数组吗，得不偿失，更何况你这10001个空间的前5000个空间没有值映射，纯纯浪费了空间，而且绝对映射不能排序负数，因为数组下标不可能为负数。这就是绝对映射的弊端，因此要用相对映射。
- 绝对映射：原数组是多少，映射到新数组下标位置++
- 相对映射：此时新数组下标的范围是从0到(原数组最大值-最小值)，而映射到下标的位置为原数组val的值 - 原数组最小min的值
图解：
综上，计数排序适用于数据有一些重复，数据范围比较集中 ，从而避免空间浪费过于严重。
- 代码如下：
//计数排序 void CountSort(int* a, int n) { int min = a[0], max = a[0]; //先求出原数组的最大和最小值 for (int i = 1; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } //求出新数组的范围 int range = max - min + 1; //开辟新数组 int* countA = (int*)malloc(sizeof(int) * range); assert(countA); //把新开辟数组初始化为0 memset(countA, 0, sizeof(int) * range); //计数 for (int i = 0; i < n; i++) { countA[a[i] - min]++; //统计相同元素出现次数（相对映射） } //排序 int j = 0; for (int i = 0; i < range; i++) { while (countA[i]--) { a[j++] = i + min; //赋值时，记得加回原先的min } } free(countA); }计数排序的缺陷：
1.只能排序整形数据，不能排序浮点数、字符串等其他类型的数据；
2.只使用与数据分布范围较小的情景，当数据分布较分散时，空间消耗太大；
注意：range = max - min + 1
时间复杂度：计数排序最终的时间复杂度为：O(N + range);
空间复杂度：计数排序需要额外开辟一个与数组用于存放映射值，开辟空间大小为相对映射最大值，也就是range，所以空间复杂度为：O(range)；
稳定性：由于统计数组可以知道该索引在原数组中排第几位，相同的元素其在原数组中排列在后面。
其从原数组的后面遍历，即反向遍历，其在最终数组中的索引也在后面，所以相同的元素其相对位置不会改变，稳定。
若从原数组的前面遍历，即正向遍历，其在最终数组中的索引在前面，相同的元素其相对位置会改变，不稳定。
计数排序特性总结
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
时间复杂度：O(N + range)
空间复杂度：O(range)
稳定性：反向遍历：稳定；正向遍历：不稳定
三.排序图表总结
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性 直接插入排序 O(N2) O(N) O(N2) O(1) 稳定 希尔排序 O(N*logN) ~ O(N2) O(N1.3) O(N2) O(1) 不稳定 选择排序 O(N2) O(N2) O(N2) O(1) 不稳定 堆排序 O(N*logN) O(N*logN) O(N*logN) O(1) 不稳定 冒泡排序 O(N2) O(N) O(N2) O(1) 稳定 快速排序 O(N*logN) O(N*logN) O(N2) O(logN) ~ O(N) 不稳定 归并排序 O(N*logN) O(N*logN) O(N*logN) O(N) 稳定
四.排序源码汇总
此篇博客有些内容还是没有涉及，因为已经太多了，还有一些测试排序性能的函数，碍于篇幅，这里没有给出。建议大家去仓库看看全部代码，以勘全貌。这里给出排序源码：Sort · wei/test_code - 码云 - 开源中国 (gitee.com)
五.总结
空间复杂度：计数排序需要额外开辟一个与数组用于存放映射值，开辟空间大小为相对映射最大值，也就是range，所以空间复杂度为：O(range)；
稳定性：由于统计数组可以知道该索引在原数组中排第几位，相同的元素其在原数组中排列在后面。
其从原数组的后面遍历，即反向遍历，其在最终数组中的索引也在后面，所以相同的元素其相对位置不会改变，稳定。
若从原数组的前面遍历，即正向遍历，其在最终数组中的索引在前面，相同的元素其相对位置会改变，不稳定。
计数排序特性总结
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
时间复杂度：O(N + range)
空间复杂度：O(range)
稳定性：反向遍历：稳定；正向遍历：不稳定
三.排序图表总结
[外链图片转存中…(img-uGGR2yzZ-1667979448453)]
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性 直接插入排序 O(N2) O(N) O(N2) O(1) 稳定 希尔排序 O(N*logN) ~ O(N2) O(N1.3) O(N2) O(1) 不稳定 选择排序 O(N2) O(N2) O(N2) O(1) 不稳定 堆排序 O(N*logN) O(N*logN) O(N*logN) O(1) 不稳定 冒泡排序 O(N2) O(N) O(N2) O(1) 稳定 快速排序 O(N*logN) O(N*logN) O(N2) O(logN) ~ O(N) 不稳定 归并排序 O(N*logN) O(N*logN) O(N*logN) O(N) 稳定
四.排序源码汇总
此篇博客有些内容还是没有涉及，因为已经太多了，还有一些测试排序性能的函数，碍于篇幅，这里没有给出。建议大家去仓库看看全部代码，以勘全貌。这里给出排序源码：Sort · wei/test_code - 码云 - 开源中国 (gitee.com)
五.总结
又是一个浩大的博客项目，比较花费时间，不过多谢三分苦大佬提供动图，不做动图可以节省不少时间。这一章节是数据结构很重要的一章，也是校招面试官喜欢考的内容，很有可能让大家直接手撕一个快排，归并排序等等，冒泡就别想了，小心面试官扁你。还是希望大家自己尝试写一写，不动笔墨，无以成书。只有自己尝试去写，才能发现自己的不足，一定要多敲代码，形成肌肉记忆，找工作的时候，直接炫技（doge保命）。
参考文章：【数据结构】八大经典排序（两万字大总结）