快速排序扩展：三路划分与自省排序，解决重复元素和最坏退化问题

快速排序扩展：三路划分与自省排序，解决重复元素和最坏退化问题

前言

普通快速排序的核心思想是：

选一个基准值key，把数组划分成左右两部分，然后递归排序左右区间。

一般情况下，快速排序的平均时间复杂度是O(NlogN)，实际性能也很好。

但是普通快排有两个比较典型的问题：

1. 当数组中有大量重复元素时，普通二路划分容易产生很多无效递归；
2. 当每次选到的基准值都很差时，快排可能退化成O(N²)。

为了解决这两个问题，在实际工程中经常会使用一些快排扩展策略。

本文主要讲两个：

• 三路划分：解决大量重复元素问题；
• 自省排序：解决最坏情况退化问题。

一、普通二路划分的问题

普通快速排序一般会把数组划分成两部分：

或者：

这种方式在随机数据下通常表现不错。

但是如果数组中有很多重复元素，比如：

inta[]={5,3,5,5,2,5,8,5,1};

如果选择5作为基准值，普通二路划分并不会把所有等于5的元素集中处理掉。

很多等于5的元素仍然可能散落在左右子区间中。

这样就会导致：

• 重复元素被反复参与递归；
• partition 做了很多无效比较；
• 递归区间缩小速度变慢；
• 极端情况下性能明显下降。

所以，当数据中存在大量重复值时，普通二路快排并不是最优选择。

二、三路划分是什么？

三路划分，也叫三向切分快排。

它的核心思想是：

不再只把数组分成“小于 key”和“大于 key”两部分，而是分成三部分。

三路划分后，数组会变成：

也就是：

[ 小于 key ][ 等于 key ][ 大于 key ]

这样做的好处是：

所有等于 key 的元素在一趟划分中就已经放到了最终位置，不需要继续递归。

后续只需要递归处理：

• 小于 key 的左区间；
• 大于 key 的右区间。

中间等于 key 的部分直接跳过。

三、三路划分的指针设计

三路划分常用三个变量：

在扫描过程中，数组大致被分成四段：

扫描规则如下：

1. 如果a[i] < key，交换a[i]和a[lt]，然后lt++，i++；
2. 如果a[i] == key，说明它属于中间区间，直接i++；
3. 如果a[i] > key，交换a[i]和a[gt]，然后gt--，但i不动。

这里自然而然会产生一个问题：为什么第三种情况中i不动？

因为从gt位置换过来的元素还没有被检查，必须再次判断。

四、三路快速排序代码实现

下面给出一个 简易的C 语言版本。

voidSwap(int*p1,int*p2){inttmp=*p1;*p1=*p2;*p2=tmp;}voidQuickSort3Way(int*a,intleft,intright){if(left>=right){return;}intkey=a[left];intlt=left;inti=left+1;intgt=right;while(i<=gt){if(a[i]<key){Swap(&a[i],&a[lt]);lt++;i++;}elseif(a[i]>key){Swap(&a[i],&a[gt]);gt--;}else{i++;}}QuickSort3Way(a,left,lt-1);QuickSort3Way(a,gt+1,right);}

五、三路划分为什么适合重复元素？

假设数组中有大量重复元素：

inta[]={5,5,5,5,5,5,5};

普通快排可能还会继续对子区间递归。

但三路划分一趟之后，整个数组都会落入“等于 key”的区间。

于是左右区间为空，递归直接结束。

所以三路划分在重复元素很多时非常有效。

可以这样理解：

普通二路快排只是在问：“比 key 小还是比 key 大？”

三路快排多问了一句：“是不是刚好等于 key？”

这一个“等于区间”，就能减少大量无意义递归。

六、三路划分的复杂度分析

三路快排的平均时间复杂度仍然是：

O(NlogN)

但在重复元素很多的情况下，它可能明显优于普通快排。

如果所有元素都相等，三路划分只需要一次线性扫描就能结束。

此时接近：

O(N)

空间复杂度主要来自递归栈。

平均情况下是：

O(logN)

最坏情况下，如果基准值选择极差，仍然可能出现递归不均衡。

所以三路划分解决的是：

大量重复元素问题。

但它不能彻底解决：

快排最坏情况退化问题。

这个问题要交给自省排序。

七、自省排序是什么？

自省排序，英文叫 Introsort，也叫 Introspective Sort。

它的名字里有 “intro”，可以理解为：

排序过程中会“观察自己”的递归状态。

自省排序的核心思想是：

一开始使用快速排序；如果发现递归深度过深，说明快排可能正在退化，就切换到堆排序；如果区间很小，就使用插入排序。

所以自省排序是一个混合排序算法。

它通常由三部分组成：

八、为什么需要自省排序？

快速排序的平均性能很好，但最坏情况下可能退化为：

O(N²)

比如数组本来有序，而每次都选最左边作为 key：

12345678

如果每次划分都极度不均衡，那么递归深度会接近N。

自省排序的处理思路是：

如果递归深度超过某个阈值，就认为快排状态不健康，立即切换堆排序。

因为堆排序的最坏时间复杂度是：

O(NlogN)

所以它可以作为快排退化时的兜底方案。

九、自省排序的 depth limit

自省排序中通常会设置一个递归深度限制。

常见写法是：

depth_limit=2*log2(n);

含义是：

正常快排的递归深度大约是logN，如果深度超过2logN，就说明划分可能不均衡。

这时候就不继续快排了，改用堆排序处理当前区间。

这个阈值不是数学上唯一固定的，而是工程上的经验选择。

它的作用是判断：

当前快排是否有退化风险。

十、自省排序的整体流程

自省排序大致流程如下：

伪代码如下：

IntroSort(a,left,right,depth_limit){if区间很小:InsertSort(a,left,right)returnifdepth_limit==0:HeapSort(a,left,right)returndiv=Partition(a,left,right)IntroSort(a,left,div-1,depth_limit-1)IntroSort(a,div+1,right,depth_limit-1)}

它不像普通快排那样“一条路走到黑”。

它会根据情况切换策略。

十一、自省排序代码骨架

下面给出一个简化版代码骨架，重点看思想。

#include<math.h>voidIntroSort(int*a,intleft,intright,intdepthLimit){if(left>=right){return;}intsize=right-left+1;if(size<16){// 小区间用插入排序InsertSortRange(a,left,right);return;}if(depthLimit==0){// 递归过深，用堆排序兜底HeapSortRange(a,left,right);return;}intdiv=PartSort(a,left,right);IntroSort(a,left,div-1,depthLimit-1);IntroSort(a,div+1,right,depthLimit-1);}voidSort(int*a,intn){intdepthLimit=2*(int)log2(n);IntroSort(a,0,n-1,depthLimit);}

这里的几个函数需要你提前实现：

• InsertSortRange
• HeapSortRange
• PartSort

在实际标准库实现中，细节会更复杂，比如 pivot 选择、小区间延迟插入排序、尾递归优化等。

但核心思想就是：

快排负责平均性能，堆排负责最坏保障，插排负责小区间优化。

十二、三路划分和自省排序的区别

三路划分和自省排序解决的问题不同。

十三、什么时候用三路划分？

如果数据中重复元素很多，优先考虑三路划分。

例如：

• 年龄排序；
• 分数排序；
• 状态码排序；
• 性别、等级、类别等小范围字段排序；
• 数据中存在大量相同 key。

比如：

9090908590708590

这种数据用三路划分会很舒服。

因为一趟划分就能把大量相同元素归到中间区间。

十四、什么时候用自省排序？

如果你想写一个更接近工程级的通用排序函数，可以考虑自省排序。

它适合：

• 数据规模较大；
• 数据分布不确定；
• 不希望快排退化成O(N²)；
• 不要求稳定性；
• 希望平均性能好，同时最坏情况也有保障。

很多标准库排序的设计思想，本质上都不是只依赖某一个基础排序算法，而是根据不同情况组合多种算法。

这也是算法工程化的重要思想：

理论上，一个算法有优点和缺点；

工程上，可以把多个算法组合起来，扬长避短。

十五、总结

普通快速排序虽然平均性能很好，但并不完美。

它主要有两个扩展方向。

第一个方向是三路划分。

它把数组划分成：

• 小于 key；
• 等于 key；
• 大于 key。

这样可以一次性处理大量重复元素，避免重复值反复参与递归。

第二个方向是自省排序。

它在快排基础上加入了“自我检查”机制：

• 普通情况使用快速排序；
• 小区间使用插入排序；
• 递归过深时切换堆排序。

这样既保留了快排的平均性能，又避免了最坏情况退化成O(N²)。