交换排序——快速排序3 针对LeetCode某OJ的优化

快速排序的优化
- 小区间优化
- 三数取中
- 三路划分优化

快速排序的优化

这篇优化围绕这个测试OJ展开。

912. 排序数组 - 力扣（LeetCode）

这个测试OJ在早期用快排还能过。但现在用快排不能过了。
请添加图片描述

因为这个OJ针对快排加了一些样例使得快排不能过这个OJ。针对这一点，下文给出优化方案。

小区间优化

小区间优化针对需要产生递归的排序算法。也就是说归并排序也能用。

我们学习排序是为了能判断所有情况，并根据情况选择合适的排序算法来处理数据。

虽然快速排序性能很优异，但并不是所有情况快排都是最优选。甚至数据量小的情况比如10个数据，快排对这10个数据排序，耗时说不定比插入排序慢。

10个数据组成的数组看成完全二叉树就是4层，递归的话还要多调用3次函数，每次调用函数都要向内存申请空间，加大时间和空间的成本。

若使用插入排序来处理这种数量比较小的数据，则减少了多余的递归调用。能使排序完成时间缩短。

以10个数据的满二叉树为例子，最底层占 $50\%$ 的结点，后层数网上逐级减半，减少3层的递归调用，优化效率 $50\%+25\%+12.5\%=87.5\%$ 。

我们可以通过chrono库的库函数和类来计算10个元素时两种排序的耗时。参考程序如下（c++程序）：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdlib.h>
#include<stdbool.h>
#include<chrono>
#include<iostream>
using namespace std;typedef int Datatype;//用的是c语言的库函数qsort
int cmp(const void* a, const void* b) {return (*(Datatype*)a) - (*(Datatype*)b);
}//插入排序
void insertSort(Datatype* a, int n) {int i = 0;for (i = 0; i < n - 1; i++) {int end = i;int tmp = a[i + 1];while (end >= 0)if (a[end] > tmp) {a[end + 1] = a[end];--end;}else break;a[end + 1] = tmp;}
}void f() {srand((size_t)time(0));Datatype a[10], b[10];int i = 0;for (i = 0; i < 10; i++) {a[i] = rand() % 1000 + 1;//随机数生成数据b[i] = a[i];}//高精度计时auto begin = std::chrono::high_resolution_clock::now();qsort(a, sizeof(a)/sizeof(a[0]), sizeof(a[0]), cmp);//用快排的库函数对10个数据进行排序auto end = std::chrono::high_resolution_clock::now();std::chrono::duration<double> time1 = end - begin;std::cout << time1.count() << endl;auto begin2 = std::chrono::high_resolution_clock::now();insertSort(b, 10);//用插入排序对10个数据进行排序auto end2 = std::chrono::high_resolution_clock::now();std::chrono::duration<double> time2 = end2 - begin2;std::cout << time2.count() << endl;//如果快排用时比插入排序用时长，则输出1，否则输出0cout << (time1.count() - time2.count() > 1e-15) << endl;
}int main() {f();return 0;
}

chrono 库的 high_resolution_clock 可以提供高精度的时间点，通过计算两个时间点的差值来得到代码执行的时间间隔， duration<double> 用于以秒为单位表示时间间隔， count() 函数返回该时间间隔的值。

用大量数据时表现不好，小量数据时表现优异的算法处理这种小规模数据的优化方式，有人称这种优化方式为小区间优化。这种优化的本质是一种锦上添花的行为，无法改变算法本身的弊端。

到这里为冒泡排序惋惜1秒钟，结束冒泡排序时至少还要枚举一遍，所以即使是小区间优化也上不了冒泡排序。

三数取中

三数取中优化可使快排的效率相对于直接用快排排序有序数据快。

三数取中即头、尾、中间取不是最差（大）也不是最好（小）的情况。三数取中优化只是对数组做一个简单的预处理，它并没有改变快排的缺陷，而是规避，使快排在排序过程中尽可能取相对中间接近中位数的值。

虽然不如直接取中位数，但直接找中位数更麻烦。要排序找，还要返回下标。

三数取中写法不固定，只要能返回取样的中间值即可。

这里给个参考程序：

//三数取中，为优化快排
//选尽可能靠近中位数的值
int GetMidIndex(int* a, int left, int right) {int mid = (left + right) / 2;if (a[left] < a[mid]) {if (a[mid] < a[right])return mid;else if (a[left] < a[right])return right;elsereturn left;}else { // a[left] > a[mid] if (a[mid] > a[right])return mid;else if (a[left] > a[right])return right;elsereturn left;}
}

三数取中优化可以放在快排的框架做数组的预处理，也可以放在单趟排序开头做预处理。

但即使是这样，上面的OJ912. 排序数组 - 力扣（LeetCode）依旧针对这种小计俩给了针对样例。

秉持道高一尺，魔高一丈的原则，我们可以尝试改进三数取中：用随机数代替中间的那个数。这个做法其实也没有比原来的三数取中做的多好，更多的是像开盲盒。也就是说依旧有一定几率抽中无法通关的数。

参考程序：

//三数取中，因为leetcode上有一题针对三数取中做出了对策样例，
//所以采取随机数取中。
int GetMidIndexRand(int* a, int left, int right) {srand((size_t)time(0));//随机数的种子int mid = left + (rand() % (right - left));if (a[left] < a[mid]) {if (a[mid] < a[right])return mid;else if (a[left] < a[right])return right;elsereturn left;}else{// a[left] > a[mid]if (a[mid] > a[right])return mid;else if (a[left] > a[right])return right;elsereturn left;}
}

三路划分优化

三种单趟排序方案都没能很好地处理存在大量重复元素的情况。所以快排无论怎么优化都无法在规定时间内通过有大量重复数据的数据组。

三路划分是快排的众多优化方式中的一种。在数据量不大的情况下，未优化的快排反而比其他排序慢。且有序的情况系更慢。但全是随机的情况快排显著更优。这个OJ就针对快排放了一些特殊的测试样例。

912. 排序数组 - 力扣（LeetCode）

这个测试样例中很多测试样例是针对快排设计的。比如某个测试样例里有个测试数据全部是2。于是就有人改进快排使得快排能应对这些场景。

若数据相等，且快排中的判断符为>=或<=，则会一路运行下去产生大量的无效递归。我们之前的三种单趟排序其实都是二路划分。所以有人提出了三路划分的优化方案。

三路划分将要排序的数据分成三路：
请添加图片描述

递归时只需要解决不等于key的部分即可，等于key的不用递归。三路划分可以认为hoare版本单趟排序和前后指针单趟排序的结合。

本质为小的排左边，大的排右边，和key相等的值排中间。

样例展示：
请添加图片描述

根据样例，给出3种情况来判断：

if(a[c]<key) Swap(&a[c],&a[l]), ++l, ++c;
if(a[c]>key) Swap(&a[c],&a[r]), --r;
if(a[c]==key), ++c

参考程序：

//快排的三路划分优化方案
//针对大量重复数据的优化
//这个方案独立于已有的快排框架
void quickSortTRoute(int* a, int begin, int end) {if (begin >= end)return;int left = begin;int right = end;int cur = left + 1;int key = a[left];while (cur <= right) {if (a[cur] < key) {Swap(&a[cur], &a[left]);++left;++cur;}else if (a[cur] > key) {Swap(&a[cur], &a[right]);--right;}else++cur;}至此，数组被划分成3个部分：            c[...,......,...]     l    r[l,r]为同一个数key，[left,l-1]比key小[r+1,right]比key大quickSortTRoute(a, begin, left - 1);quickSortTRoute(a, right + 1, end);
}

即使是三路优化，依旧存在这样的样例无法用快排进行排序：无法准确找到中位数，也无法找到哪个数重复最多，特别是找三数全是最小的或最大的（三数取中的针对设计样例）。

即使是这样，依旧可以设计新的三数取中：用随机数代替中间的那个数。详细见上文的三数取中。

三路划分只是针对复杂情况做的对策，实际效率比快排本体慢，平时用正常的快排就行。

而无论那种预排，当key选中中位数时效率最高，此时相当于二分算法。除了这种极其好运抽到中位数的情况，快排少部分情景用别的排序更优，更多场景快排几乎是最优。弄清排序的意义是极端情况下有多重选择，可以设计出达到预期的排序算法（除了某冒泡排序实在救不回来）。

到这里，给出OJ912. 排序数组 - 力扣（LeetCode）的快排解法：

//快排的三路划分再优化方案
//因为leetcode上有一题针对三数取中做出了对策样例，
//所以采取随机数取中。
void quickSortTRoute(int* a, int begin, int end)
{if (begin >= end)return;int left = begin;int right = end;int cur = left + 1;//针对leetcode的三数取中对策做的下策：随机数取中int midi = GetMidIndexRand(a, begin, end);Swap(&a[midi], &a[left]);int key = a[left];while (cur <= right) {if (a[cur] < key) {Swap(&a[cur], &a[left]);++left;++cur;}else if (a[cur] > key) {Swap(&a[cur], &a[right]);--right;}else {++cur;}}quickSortTRoute(a, begin, left - 1);quickSortTRoute(a, right + 1, end);
}