一篇文章带你完美拿下快速排序的三个版本（附带随机取数、三数取中、三路划分、小区间优化等细节功能优化讲解）！

快速排序

• 前言
• 一、快速排序是什么？
• 二、快速排序的实现
• • • • 1.Hoare版本
      • • Hoare版本示例过程拆分讲解
      • 2.挖坑法
      • • 挖坑法示例过程拆分讲解
      • 3.前后指针法
      • • 前后指针法示例过程拆分讲解
• 三、为什么要用快速排序
• • • • 1.快速排序平均情况和最好情况下的时间复杂度计算
      • 2.最坏情况下时间复杂度的计算
• 四、快速排序的优化与细节讲解
• • • • 1.为什么keyi取left位置时，要让right先走？为什么keyi取right位置时，要让left先走？为什么这样可以保证排序正确？
      • 2.如何选keyi值才能使程序更加高效？如果遇到已经有序的数据退化成O（N²）的时间复杂度该怎么办？
      • • 1.随机取数法取keyi值
        • 2.三数取中法取keyi值
      • 3.三路划分是什么？排序时遇到大量重复元素该怎么办？
      • 4.小区间优化
      • 5.随机取数与三数取中的结合使用
• 五、快速排序的稳定性

前言

本篇讲解快速排序

一、快速排序是什么？

快速排序是一种排序算法，由Hoare大佬于1962年提出，顾名思义，它是一种快速、高效的排序算法。

快速排序算法是冒泡排序的一种改进，也是采取分治思想进行排序的一种算法我们以升序为例进行讲解，快速排序的实现方法就是将大的数往右边抛，将小的数往左边抛

具体实现方法是在给定的一组数据里找定一个值当作keyi，以keyi为基准，对其进行排序，要求排序后keyi左边的值要全部小于等于keyi，keyi右边的值要全部大于等于keyi，此时keyi的具体位置就确定了，我们以keyi作为切分点，划分区间，分为左右两组，那么在左边的数据中新找一个keyi值，在右边的数据中也新找一个keyi值，此时对左右两组的数据同时进行之前的排序操作，依旧是要求左边全部小于等于keyi，右边全部大于等于keyi，重复递归操作直到成为有序状态

上述操作的展开图类似于二叉树，如下图理想状态下所示

在这个过程中，我们的操作是先令数组整体有序，再一步步地使其局部有序，类似于二叉树的先序遍历

二、快速排序的实现

1.Hoare版本

大家可以先看下图了解一下hoare方法的单趟运行过程

Hoare是一个大佬的名字，他于1962年首次提出快速排序的概念，后面经发展后衍化出多个版本，而最初的快速排序的方式则被称为Hoare版本快速排序

我们以升序排序为例进行讲解：

Hoare法的主要思想是定义一个left指针和一个right指针，left在数据开始，right在数据末尾，选定一个keyi值后（假定我们选在left），此时我们就要先移动right指针，right往前寻找比keyi小的值，如果right对应的值大于等于keyi对应的值，那么right- -，如果小于keyi，那么right指针停止不动，开始移动left指针；如果left指针对应的值小于等于keyi对应的值，那么left++，如果大于keyi，那么left指针停止不动，此时交换left指针与right指针的对应值，接着重复上述操作，先移动right，再移动left，直到两者相遇，相遇后交换相遇位置的值与keyi的对应值，此时相遇位置便是切分点，切分点左边的值全部小于等于切分点对应的值，切分点右边的值全部大于等于切分点对应的值，代表这一趟排序完毕，进入下一趟排序

这一趟排序完毕后，我们以切分点为中点，将整体数据切分成两个区间，即切分点左边的所有数据与切分点右边的所有数据这两个数据区间，之后对这两个区间分别重复上述步骤，值得一提的是，我们此处对快速排序划分出的子区间进行排序，往往是符合先序遍历的，因为我们的执行逻辑是一条一条语句往下执行的，而当我们采取递归形式时，便是先不断递归到第一次划分出的其中一个子区间的最深处，即区间内只有甚至没有数据的时候，这时候是不断往上压栈的，之后排序完成后销毁，再接着执行第一次划分出的另一个子区间

如代码所示：

void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left, end = right;
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right—;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
QuickSort(a, begin, left – 1);
QuickSort(a, left + 1, end);
}

Hoare版本示例过程拆分讲解

如代码所示，我们以动态图再作一次讲解：

我们可以看到，这是最初状态，left小兵在数据初始位置，right小兵在数据末尾，我们选定left为keyi基准值，那么right小兵就要先行进发

如图所示，right小兵要找比目标值keyi小的值，当大于等于keyi值时，就会一直往前走，即right- – ， 而当right小兵遇到5时，判断5小于6，便在5的位置停下，此时left小兵开始移动； left小兵要找比目标值keyi大的值，当小于等于keyi值时，就会一直往前走，即left++， 而当left小兵遇到7时，判断7大于6，便在6的位置停下 两者都停下后，进行值的交换，交换完毕后right小兵继续向前走，寻找小值。

如图所示，当right小兵开始往前走，走到4的位置时，判断4小于6，right小兵停止，left小兵开始移动 left小兵走到9的位置时，判断9大于6，left小兵停止 此时交换left小兵与right小兵对应的值，交换后继续移动right小兵

如图，right继续向前走，走到3的位置时，判断3 小于6，right小兵停止不动，left小兵开始移动 left小兵走到3的位置时，和right小兵相遇，相遇后原地交换（left与right位置对应值交换，即自身与自身进行交换），交换后循环结束

如图，循环结束后，将keyi值与相遇位置的值进行交换，之后以相遇点作为切分点，左边分成一个区间，右边分成一个区间，再对两个区间分别进行重复操作即可

值得一提的是，我们将上图中的{3，1，2，5，4}这组数据区间称作区间A1，代表第一次划分区间后得到两个子区间中的左边的区间，那么根据代码执行的话，我们会先对区间A1进行排序，对区间A1进行排序后，又会分成两个子区间，即B1和B2，这两个子区间组合起来就是区间A1 如图： 那么按照代码顺序，要先对区间B1进行排序，而在区间B1中，经过排序后，便可以划分为区间C1和区间C2，接着又先排序区间C1，后面依次往下执行，示意图如下：

2.挖坑法

挖坑法单趟排序如下所示： 代码如下：

void QuickSort2(int* a, int left,int right)
{
if (left >= right)
{
return;
}
int begin = left, end = right;
int keyi = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= keyi)
{
right—;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= keyi)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = keyi;
QuickSort(a, begin, hole – 1);
QuickSort(a, hole + 1, end);
}

本方法的主要思想就是选定一个位置作为坑（hole），假定我们选定left为坑，保存第一个坑位对应的值，之后right要先开始走，规则与之前类似，我们right在走的时候，如果遇到大于等于第一个坑值的数便跳过，即right- – ，如果遇到小于第一个坑值的数便停下，此时该位置成为新的坑位，并将新坑位的值赋给旧坑位，之后再移动left，规则与right相同，遇到小于等于第一个坑值的数便跳过，即left++，如果遇到大于第一个坑值的数便停下，赋值并使其成为新的坑位，直到两者相遇才停下，最后将第一个坑位对应的值赋值给最后的新坑位，此时完成一趟排序

完成一趟排序之后，最后的新坑位，即left与right的相遇点，便是区间的切分点，此时新坑位左边的值均是小于等于切分点的，新坑位右边的值均是大于的等于切分点的，后面重复操作子区间即可

挖坑法示例过程拆分讲解

如下图，我们定义第一个坑位在left位置，用keyi来存储第一个坑位对应的值

之后开始移动right小兵，与之前的规则相同，right小兵要寻找的小于keyi的值，如果大于等于就继续往前走，即right- – 当right小兵走到5的时候，判断5小于6，right小兵停止不动，此时right小兵所在位置成为新的坑位，并将对应的值赋给旧坑位，之后left小兵开始移动

left小兵要找的是比keyi大的值，遇到小于等于的值直接跳过，即left++ 当left遇到7的时候，判断6小于7，此时left停止不动，并且成为新的坑位，将left对应的值赋值给旧坑位（此时的旧坑位是right所在的位置），随后right开始移动

当right走到4时，判断4 小于6，那么right停止移动，并成为新的坑位，并将新坑位的值4赋给旧坑位，即left所在位置，此时left开始移动

当left走到9时，判断9大于6，此时9成为新的坑位，并将9赋值给旧坑位，之后right开始移动

当right走到3时，判断3小于6，right停止，并成为新的坑位，将3赋值给旧坑位，此时left开始移动

当left走到3时，此时left与right相遇，判断条件结束，循环结束，此时将第一个坑位的值keyi赋值给相遇点，相遇点左边的数据便全部是小于等于相遇点的，右边的数据全部是大于等于相遇点的，此时便可以以相遇点作为切分点，划分为两个区间，后续思路便同hoare类似，具体操作则重复上述操作即可

3.前后指针法

前后指针法的单趟排序过程如下： 代码如下：

void Swap(int* a, int* b)
{
int tmp = *b;
*b = *a;
*a = tmp;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = left;
int begin = left, end = right;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
QuickSort(a, begin, prev – 1);
QuickSort(a, prev + 1, end);

}

该方法的主要思想是定义一个prev指针和一个cur指针，我们定义基准值keyi在left的位置，prev在left或是right均可，我们假定在left，与基准值重合，此时cur在prev+1的位置

我们的cur指针与left指针都要往前走，cur指针是寻找比keyi对应值小的值

当开始排序时，cur先出发，当遇到大于等于keyi值的数据时，cur++，prev指针不动；当遇到小于keyi值的数据时，cur指针停下，prev++，然后交换prev与cur对应的值，交换后cur继续往前走，重复上述步骤

直到cur大于right时，循环结束，交换此时prev与keyi的值，此时排序结束，prev左边的数据全部小于等于prev对应值，右边的数据全部大于等于prev对应值，此时prev便可作为切分点，划分出左右两个区间

而按照代码中显示的，我们判断当cur对应值小于keyi，并且prev+1之后不等于cur时，才交换cur和prev的对应值，这是简化的版本，比如{3，1}这组数据，我们的left是3，prev指向3，cur指向1，判断3大于1，那么prev++，指向了1，这时候交换prev和cur的对应值，相当于自身进行交换，是没有必要的，因此当prev+1后仍然和cur之间隔着许多数据时，我们再进行交换即可

完整按照思想进行代码如下：

void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = left;
int begin = left, end = right;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
while (cur <= right && a[cur] >= a[keyi])
{
cur++;
}
if (cur <= right && a[cur] < a[keyi])
{
prev++;
Swap(&a[prev], &a[cur]);
}
}
Swap(&a[prev], &a[keyi]);
QuickSort(a, begin, prev – 1);
QuickSort(a, prev + 1, end);

}

前后指针法示例过程拆分讲解

如图，这是排序前的最初状态，此时cur指针开始移动，寻找比keyi小的值

cur指针在1的位置时，判断6大于1，那么cur指针停止不动，prev指针++，交换prev和cur对应的值，此时相当于自身与自身进行交换，交换后cur指针继续移动

cur指针移动到2的位置，判断6大于2，cur指针停止不动，prev指针++，此时prev指向2，cur也指向2，prev的对应值和cur的对应值进行交换，此时依然是自身交换，交换后cur指针继续移动

此时cur走到7的位置，判断7大于6，prev不动，cur继续往前移动，即cur++

当cur指针走到9时，判断6小于9，cur继续移动，移动到3时，判断3小于6，此时cur停止，prev++ ， 在 prev++后，指向了7的位置，此时交换cur和prev的对应值，交换后cur继续往前走，即cur++

当cur走到4的位置时，判断4小于6，此时cur停止，prev++ 在 prev++后，指向了9，此时交换prev和cur的对应值，交换后cur继续++，寻找小值

cur走到5的位置时，判断5小于6，cur停止不动，prev++ 在prev++后，指向了7的位置（原本是3，此时已交换，数值变为7），此时交换prev和cur的对应值，交换后cur继续++

当cur遇到10，8两个数字时，均判定大于6，于是cur一直++，直到cur大于right时，判断条件结束，循环终止，cur停止，prev也停止 循环结束后，交换此时prev的对应值与keyi的对应值，我们可以看到，prev所在的位置，对应值由3变为7，又变成5，最后变为了6，此时prev左边的值全部小于prev对应值，右边的值全部大于prev对应值，我们便可以prev为切分点，划分出两个区间，[begin,prev – 1]和[prev + 1,end]，后续重复操作即可

三、为什么要用快速排序

1.快速排序平均情况和最好情况下的时间复杂度计算

评价一个排序算法的好坏要从多个角度去考虑，比如它的限制条件、时间复杂度、空间复杂度等等，我们来计算一下快速排序的时间复杂度 如图，我们假定每次划分区间都是均分，即类似二叉树的结构，每次都平分区间，那么假定共要分h次，分到区间只有一个数或者没有才停止，所以2 ^h = n，h = logN,即一共需要分logN次

同时，尽管我们的快速排序是先序遍历，但在排序总次数上是不变的，只是排序区间的先后顺序不同而已， 如上图分成的子区间A1，对应的另一个子区间{9，7，10，8}我们称其为区间A2，我们的执行顺序虽然是按照区间A1->区间B1->区间C1->…的顺序，执行到底后再返回从最底部的右子区间开始逐个往上执行直到执行完区间B2，再进行区间A2的执行，但是这只是执行顺序的先后问题，并不代表某个数据个数大于1的区间没有进行排序

也就是说，区间A1和区间A2都要进行排序，同时，区间A1划分出的区间B1和区间B2，以及区间A2划分出的区间B3和区间B4，也都需要进行排序

而按照我们的快速排序思路，一组个数为n的数据，每次单趟排序都要将除基准值之外的n-1个数据与与其进行比较，有时候甚至会走到基准值，再进行一次边界的判断（比如此时left = right），也就是说，我们每一次单趟排序，要排序的次数量级是n次左右，即快速排序的每一次单趟排序的时间复杂度都是O(N)，而我们一共分了logN次，那么总排序次数自然就是N*logN，那么时间复杂度就是O(NlogN)，当然，这是最好情况与平均情况的时间复杂度，因为我们是按照每次划分区间都是平分来计算的，但事实上不一定每次都会平分，因为我们无法确定keyi值在整个区间中的位置，只有排完序才可知道

2.最坏情况下时间复杂度的计算

而当处于最坏情况的时候，那便是每次划分区间都是只有一个区间，即n个数据，第一趟排序后划分为空区间和包含n-1个数据的区间 如下列1-8的有序区间，我们并不知道这组数据有序，要对他进行排序

而right指针需要找的是小于keyi值的数，但是该数据本身已经有序，因此keyi右边的数据全部大于等于keyi，因为right最后会直接和left相遇，也就是到了keyi的位置，此时left和right对应值交换，此时即交换自身，交换后循环结束，再将keyi和相遇点的值交换，此时也是自身和自身交换，交换后排序结束，此时相遇点作为切分点，划分出左右两个子区间

但是此时相遇点的左边已然没有数据，而右边则是剩下的所有数据，即我们所说的n-1个数据，那么我们接下来就要直接对这n-1个数据区间进行上述操作，排序完后得到的是包含n-2个数据的有序区间，再对其进行重复操作，那么总排序过程就是n—>n-1—>n-2—>n-3—>…—>3—>2—>1

总排序次数便是1 + 2 + 3 + … + n – 2 + n – 1 + n = n * (n + 1) / 2，由此得到时间复杂度为O(N²)

由此可知，快速排序最坏情况下的时间复杂度会退化成O(N²)

可见，快速排序的时间复杂度并不稳定，最坏情况可达O（N²），但是它的效率还是远远优于冒泡排序等排序算法的，最优情况和平均情况均为O(N * logN)，此时在处理大规模数据时效率相差是极大的，例如： 经过计算分析我们可以得知，当数据量过大时，快速排序的效率远高于O(N²)的排序算法

四、快速排序的优化与细节讲解

1.为什么keyi取left位置时，要让right先走？为什么keyi取right位置时，要让left先走？为什么这样可以保证排序正确？

当keyi取left位置时，要让right先走，此时可以保证相遇点左边全部是小于等于keyi的数据，右边全是大于等于keyi的数据；

同理，当keyi取right位置时，要让left先走，此时可以保证相遇点左边全部是小于等于keyi的数据，右边全是大于等于keyi的数据

原因是什么呢？

让我们拿Hoare版本举例，根据我们上面的步骤拆分讲解，我们可以看到，当keyi在left位置时，此时right指针先开始移动

当right指针移动到大于等于keyi的数据时会直接跳过，当right移动到小于keyi的数据时，就会停下，此时left开始移动，left移动到大于keyi的数据时，就会停下，并与right的数据进行交换，此时right指向的小数据会被甩到左边，而left指向的大数据会被甩到右边，交换之后right指向的大于等于keyi的值，left指向的是小于等于keyi的值，之后right继续前进，重复上述步骤

而最后两者相遇时一定是right去寻找left，或者是left去寻找right，只有这两种情况

当right去寻找left时，一种情况是两者进行交换后（此时right右边的值没有小于keyi的，left左边的值没有大于keyi的），right与left之间没有小于keyi的值了，right- – 一路直接与left相遇 而两者进行交换后，right指向的大于等于keyi的值，left指向的是小于等于keyi的值，那么当right与left相遇时，相遇点的数据仍然是小于等于keyi的值，此时相遇点的值与keyi的值进行交换，相当于把相遇点的小值往左边甩了，交换后相遇点左边的值全部是小于等于keyi的，右边的值全部是大于等于keyi的

第二种情况则是两者并没有进行交换，即整组数据是有序的，right直接到达了keyi的位置，此时相遇点即是keyi，此时交换后仍然是保证了相遇点左边全部是小于等于keyi的数据，右边全是大于等于keyi的数据的情况，只是左子区间并没有数据，右子区间包含剩下的n-1个数据而已

当left去寻找right时，必定是right找到了小于keyi的值时停下了（此时可以确定right右边的值中没有小于keyi的值），left++一路寻找没有寻找到大于keyi的值，最后两者相遇，相遇点的数据是right指向的小于keyi的值，此时将keyi的值与相遇点的值交换，还是相当于把相遇点的小值往左边甩了，交换后相遇点左边的值全部是小于等于keyi的，右边的值全部是大于等于keyi的

至于left去寻找right在大于keyi的值的位置相遇这种情况是不可能的，因为right只有找到小于keyi的值或者是和left相遇才会停下来，前者自然不必多说，后者相遇，只存在left停下，right去寻找的时候才可能找到大值，但是这与前提相矛盾，并且再推导就回到第一种情况，因此两者相遇点的值必定是小于等于keyi的

至于keyi最初在right位置时，过程也与上述相同，只是要让left先走罢了

下面我们模拟一下当keyi在left位置时，如果不让right先走，而是left先走，会出现什么

如果说left先走的话，那么left会一直++，直到找到比keyi大的值，找到之后停下，接着right开始找小，找到小的值之后，两者进行交换，此时left指向小的值，right指向大的值，暂且看起来没有什么错误

但是当两者相遇时，也是分为right寻找left与left寻找right两种情况

当right寻找left时，因为我们讨论的是left先动，那么left必然已经停止，并且指向的是大于keyi的值，如果right直接与left相遇，那么相遇点的值便是大于keyi的值，此时与keyi进行交换，会导致相遇点左边存在大于相遇点的值，这就不符合区间划分的要求

如果是left寻找right，那么第一种情况是right没有移动，left直接去寻找right，此时我们并不知道right指向的是小于keyi的值还是大于keyi的值，因此存在错误风险

第二种情况是right和left已经进行过交换，此时right指向了比keyi大的值(因为left先找到大值后停下，right去找小值，找到后两者进行交换，交换后right自然指向了大值，而left自然是指向了小值)，两者相遇后与keyi值进行交换，会导致大的值跑到相遇点的左边，此时相遇点左边存在了比keyi大的值，这不符合快速排序区间划分的要求，会出现错误

因此当keyi取left位置时，要让right先走，此时可以保证相遇点左边全部是小于等于keyi的数据，右边全是大于等于keyi的数据； 同理，当keyi取right位置时，要让left先走，此时可以保证相遇点左边全部是小于等于keyi的数据，右边全是大于等于keyi的数据

2.如何选keyi值才能使程序更加高效？如果遇到已经有序的数据退化成O（N²）的时间复杂度该怎么办？

针对选keyi值，我们上面讲述过，如果一直固定选最左边作为基准值keyi，那么遇到已经有序的数据时，快速排序的时间复杂度就会退化为O(N²)，会让效率大幅度降低，那么我们该如何避免呢？

针对这种情况，我们提供了两种方法

1.随机取数法取keyi值

void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int randi = left + (rand() % (right – left));
Swap(&a[left], &a[randi]);
int keyi = left;
int begin = left, end = right;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
while (cur <= right && a[cur] >= a[keyi])
{
cur++;
}
if (cur <= right && a[cur] < a[keyi])
{
prev++;
Swap(&a[prev], &a[cur]);
}
}
Swap(&a[prev], &a[keyi]);
QuickSort(a, begin, prev – 1);
QuickSort(a, prev + 1, end);
}

假定给我们一个有序数组，我们依然保持keyi选的是left，但是此时left对应的值已经和区间里的某个其他数进行了交换，这就打破了有序状态，因此随机取数可以用来减缓有序数组导致的效率退化问题，但是不能完全避免，因为它是随机的

2.三数取中法取keyi值

int GetMidNum(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[mid] < a[left])
{
if (a[right] < a[mid])
{
return mid;
}
else if (a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[right] > a[mid])
{
return mid;
}
else if (a[right] < a[left])
{
return left;
}
else
{
return right;
}
}
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int mid = GetMidNum(a, left, right);
if (mid != left)
{
Swap(&a[mid], &a[left]);
}
int keyi = left;
int begin = left, end = right;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
while (cur <= right && a[cur] >= a[keyi])
{
cur++;
}
if (cur <= right && a[cur] < a[keyi])
{
prev++;
Swap(&a[prev], &a[cur]);
}
}
Swap(&a[prev], &a[keyi]);
QuickSort(a, begin, prev – 1);
QuickSort(a, prev + 1, end);
}

三数取中的思想就是选定中间的位置，将中间位置对应的值，left对应的值，right对应的值这三个数比较出大小，取中间的数，这样可以打破有序，因为我们并不知道有序的数组是升序还是降序，无论我们取大取小都有风险，因此我们直接取中间的数即可，这样可以稳定打破有序状态

3.三路划分是什么？排序时遇到大量重复元素该怎么办？

当我们排序时，不仅会遇到已经有序的数组，比如降序升序都可以，还会有可能遇到大量重复甚至完全重复的数据，比如{1，2，2，2，2，2，2，2，2，2}这种，甚至是{2，2，2，2，2，2，2，2}，当我们对这组数据进行排序时，会导致快速排序的性能退化，因为这就类似于有序数组了，大家可以自己模拟一下，最后退化成接近O(N²)的时间复杂度

那么我们为了解决这种情况，就研究出了三路划分这种思想

三路划分的主要思想就是，将整组数据划分为三个区间，一个左边的区间，全部小于keyi值，一个中间的区间，全部等于keyi值，一个右边的区间，全部大于keyi值。而中间等于keyi值的区间就不需要再进行排序了，我们只需要对左右两边小于或者大于keyi值的区间进行排序即可，我们可以定义一个cur指针，它指向left指针的下一位，cur一直往前走

当cur遇到和keyi值相等的数据，就跳过，将它留在原地

当cur遇到比keyi值大的数据，就要像之前的思路一样，将大的值往后推，也就是推到右边，那么就和right互换，互换后right- -，但是cur不能动，因为cur一旦往前走，就会将right原本指向的值留下，我们无法确定该值是大于keyi还是小于keyi亦或是等于keyi，因此right并没有进行判断，因此cur不能动

right- – 后，cur继续判断，如果判断遇到比keyi小的值，那么就要将该值往左边甩，即需要和left互换，互换后，left指向的是比keyi小的值，cur指向的小于等于cur的值，此时必须移动left和cur

因为如果不移动left，那么若下一步判断出cur指向的值小于keyi，那么就会和left进行交换，此时小值又被甩到了右边去，这是有一定风险导致右区间出现比keyi小的值的情况的，因此left必须移动。而cur也要移动，因为keyi是固定的值，cur指向的值交换后可能小于keyi也可能和keyi相等，如果相等，自然就是cur++，这个没问题，但如果小于keyi，就会导致死循环，因此此时left指向的也是比keyi小的值，所以left和cur必须同时移动

有的同学可能提出如果只移动left但是不移动cur可不可以，那么我们来讨论一下，如果只移动left的话，当left指向的值小于keyi时，cur指向的值自然也会一直小于keyi（一直在交换），那么就会一直交换，那么left一定会超过cur，如果超过cur之后，left在移动期间恰好指向了某个大于keyi的值，就会导致小值被抛向右边，大值抛向左边，此时cur指向大于keyi的值，与right交换，right无论指向的是大值或是小值，都会导致有一个小值被留在右边，这种情况下甚至有可能导致left超越right

而如果right指向的是相等元素的话，那么cur就会++，此时可能会造成cur与left相遇，这时候left指向的是之前抛过来的小值，此时原地交换，left再++，left又跑到了cur的前面，当cur与right相遇的时候，存在极大的越界风险，因此要让cur和left同时++

代码如下：

void QuickSort2(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int mid = GetMidNum(a, left, right);
if (mid != left)
{
Swap(&a[mid], &a[left]);
}
int keyi = a[left];
int begin = left, end = right;
int cur = begin + 1;
while (cur <= right)
{
if (a[cur] > keyi)
{
Swap(&a[right], &a[cur]);
right—;
}
else if (a[cur] == keyi)
{
cur++;
}
else
{
Swap(&a[cur], &a[left]);
left++;
cur++;
}
}
QuickSort2(a, begin, left – 1);
QuickSort2(a, right + 1, end);
}

4.小区间优化

通过之前的讲解，我们可以知道，当快速排序每次划分区间都均分的话，时间复杂度会是O(N*logN)，类似于二叉树，那么我们将其完全展开的话，如下图所示： 我们类比二叉树的图片来看，可知高度为h的二叉树总节点个数为2^h – 1，而最后一层却是有2 ^ (h – 1)个节点，这可以说是占了总节点个数的一半，而倒数第二层是2 ^ (h – 2)个，可以说是占了四分之一，那么单单最后两层就已经占了四分之三的数量

而通过我们的计算，从最后一层到倒数第十层（大于等于10时）的节点总数占据了99.9%的总节点个数，也就是说，在快速排序中，最后十层划分区间的次数占据了划分区间总次数的99.9%

而根据快速排序区间划分的规则，从倒数第一层开始，倒数第一层的每个区间内的元素个数为1，或者0，每上一层，每个区间内的元素个数就增加1，由此可以知道，就算到了倒数第十层，每个区间内的元素个数也不过10个左右，此时我们可以采取任意方法进行排序，O(N²)与O(NlogN)方法的效率相差都不大，但是当我们舍弃快排采用其他排序方式时，却节省了99.9%的划分次数，这对效率的优化是很大的，因为快排里时间复杂度N*logN中的logN就是划分的总次数所在的量级，节省99.9%之后，效率必然会大大提升

代码如下：

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)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end—;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void Swap(int* a, int* b)
{
int tmp = *b;
*b = *a;
*a = tmp;
}
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
{
return;
}
if (right – left + 1 <= 10)
{
InsertSort(a + left, right – left + 1);
return;
}
int mid = GetMidNum(a, left, right);
if (mid != left)
{
Swap(&a[mid], &a[left]);
}
int keyi = a[left];
int begin = left, end = right;
int cur = begin + 1;
while (cur <= right)
{
if (a[cur] > keyi)
{
Swap(&a[right], &a[cur]);
right—;
}
else if (a[cur] == keyi)
{
cur++;
}
else
{
Swap(&a[cur], &a[left]);
left++;
cur++;
}
}
QuickSort2(a, begin, left – 1);
QuickSort2(a, right + 1, end);
}

我们在快速排序划分到小区间时，采取的排序方式是插入排序，因为我们在经过前几次的排序之后，该组数据已经相对比较有序了，而插入排序针对相对有序的数据进行排序的效率是非常高的

并且，我们在传参数时，传递的是a + left和right – left + 1，因为我们并不知道我们要排序的区间是C1、C2还是D5亦或者是D7，因此我们要给a的起点加一个left，找到要排序区间的起点，区间数据个数则是right-left+1，因为是左闭右闭区间，此时便完成了小区间优化

5.随机取数与三数取中的结合使用

前面我们讲到，为了解决有序数组的出现，我们采取三数取中和随机取数的方法来缓解，乍一看三数取中是更加稳定的，但是在某种极端情况下，三数取中是无法起到相应的作用的

下面附一道题，本题就是典型的例子

题目链接：https://leetcode.cn/problems/sort-an-array/description/ 该题存在一种极端情况的测试用例，如果我们采用快速排序去解决的话，那么当你使用三数取中的时候，它会每次都恰好取到区间的边界，也就是说会退化成无三数取中无随机取数时对有序数组进行快速排序的情况，这时候的效率会大大退化，甚至有可能会退化到O(N²)，导致超出时间限制，而随机取数可以解决这一问题，但是随机取数并不是那么的稳定，因为它是随机的，某种极端情况下，它也甚至也会一直取到边界，使得效率退化，因此我们要两种方法结合使用

当结合使用时，这道题是可以过的 代码如下：

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void Swap(int* a,int* b)
{
int tmp = *b;
*b = *a;
*a = tmp;
}
int GerMidNum(int* a,int left,int right)
{
int mid = (left + right) / 2;
if(a[mid] > a[left])
{
if(a[right] > a[mid])
{
return mid;
}
else if(a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else
{
if(a[right] < a[mid])
{
return mid;
}
else if(a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
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)
{
if(tmp < a[end])
{
a[end + 1] = a[end];
end—;
}
else
{
break;
}
}
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 randi = left + (rand() % (right – left));
Swap(&a[left], &a[randi]);
int mid = GerMidNum(a,left,right);
if(mid != left)
{
Swap(&a[mid],&a[left]);
}
int begin = left,end = right;
int keyi = a[left];
int cur = begin + 1;
while(cur <= right)
{
if(a[cur] < keyi)
{
Swap(&a[cur],&a[left]);
left++;
cur++;
}
else if(a[cur] > keyi)
{
Swap(&a[right],&a[cur]);
right—;
}
else
{
cur++;
}
}
QuickSort(a,begin,left – 1);
QuickSort(a,right + 1,end);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
QuickSort(nums,0,numsSize – 1);
return nums;
}

我们同时采取随机取数和三数取中两个方法来确定基准值，这可以大大避免极端情况的出现（两种方法谁在前谁在后均可）

五、快速排序的稳定性

注意，关于排序算法的稳定性，一般指的是相同数据之间相对顺序的稳定性，而不是时间复杂度的稳定性

所谓数据之间相对顺序的稳定性，就是指在{a1,a2,3,8,1}这个数组，其中a1和a2是相等的，排序之前的顺序是a1在a2前面，排序后无论是{a1,a2,1,3,8}还是{1,a1,a2,3,8}只要a1在a2前面，就可以说这两个数据的相对顺序是稳定的，如果在一组数据中，完全排序完毕后，任意两个相同数据都满足上述条件，那么就称这个排序是稳定的

对于某些排序，我们只要改变条件就可以使它稳定，亦或者使它不稳定，只要我们能使它稳定，就可以说它是稳定的排序，但是快排显然不具备这种条件

如果出现{1，3，8，a2，a1}这种情况，就说明是排序不稳定的

而快速排序必然是不稳定的，因为在快速排序中，我们的规则是将小的值全部甩向左边，大的值全部甩向右边，最后交换相遇点和keyi的值，而交换后，大部分情况都会出现相遇点左右两边存在等于keyi值的数字，此时相对顺序已然改变，后面无论如何排序都是不稳定的

举个例子，{2a，2b，1a，1b}，2a = 2b,1a = 1b，那么对它进行快速排序 第一趟排序后，变为了{1b,2b,1a,2a}，划分出区间{1b,2b,1a} 第二趟排序后，变为了{1b,2b,1a}，划分出区间{2b,1a} 第三趟排序后，变为了{1a,2b},划分出区间{1a} 最后得到{1b,1a,2b,2a}，此时相对顺序改变，说明该排序并不是稳定排序

即使改变条件，例如改为相等的数据也要交换（在快速排序中相等的数是跳过去的），也无法达到稳定