(a4)快速排序：变种

官官方信息技术老师·15 页·深入（追求细节与边界）·0 次浏览·38 天前
✦ (a4)快速排序：变种信息技术(a4)快速排序：变种: 实现
排序算法递归基准选取

快速排序：变种

看懂快排为何退化，以及各变种如何逐个堵住这些漏洞

按 空格/→ 演示下一步

问一句
1 / 15 页

全部页面点击任意一页，跳回舞台从这页播放

排序算法递归基准选取

快速排序：变种

看懂快排为何退化，以及各变种如何逐个堵住这些漏洞

1第 1 页 · 快速排序：变种

变种地图

从中心出发：所有变种都在解决同一个问题——轴点怎么选，选得好坏决定快排的效率。

图解渲染中…
root：轴点(pivot)是每轮划分的分界基准值b2：三路快排：把等于轴点的元素单独分一段a3：取首、中、尾三个数的中位数当轴点
2第 2 页 · 变种地图

轴点与划分

上一页的变种地图里，所有分支最终都回到同一个动作：选定轴点，一趟扫过去把它安放到位。这页就拆开看这个共同骨架——轴点落位后到底发生了什么。

轴点
选定的基准元素，一趟划分后停在最终位置
划分
把小于轴点的放左、大于的放右，无需有序
独立递归
左右两段互不影响，各自重复同样过程
边界
相等元素归哪边、区间为空如何终止，决定实现细节
排队报数分堆对应 →划分过程

报数者站位对应轴点落位，矮个左高个右两堆再各自重排

quick(a,l,r):  p=partition(a,l,r)  ⇒  quick(a,l,p−1),  quick(a,p+1,r)quick(a,l,r):\; p=\text{partition}(a,l,r)\;\Rightarrow\; quick(a,l,p-1),\; quick(a,p+1,r)
3第 3 页 · 轴点与划分

不变性：划分过程中的守恒

上一页我们说，划分要把序列劈成「小于轴点」和「不小于轴点」两半。可劈的过程中，轴点自己先被抠出来放一边，中间状态千变万化——凭什么最后一定是对的？靠的是每一步都守住的几条「铁律」。

轴点暂存
轴点先抠出存入临时变量，序列里留一个空位
候选轴点
暂存的值就是最终轴点候选，全程不变
左右已就位
空位一侧的元素都已确认与轴点的大小关系
交换填坑
每次从另一侧找违规元素填空位，空位翻转
终止守恒
左右指针相遇处即轴点归宿，不变式保证正确
搬家里腾空房间对应 →挖坑填坑划分

先腾出一间空房（暂存轴点），再不断把不符的物品换入空房，空房位置移动

4第 4 页 · 不变性：划分过程中的守恒

单调性：循环变量的推进

上一页我们守住了划分的不变性，但有个隐含问题没回答：为什么划分一定会做完？如果两个游标来回踱步、甚至互相错过不停下，循环就永远不会结束。这一页看它们的推进方向。

hi 单调左移
hi 从右端出发，每次判定后只减不增
lo 单调右移
lo 从左端出发，交换后只增不减
不回头=终止
两者推进量逐次累加，有限步内必相遇，循环结束
单调支撑不变性
正是逐格推进，才让不变式在每一步都保持成立
两人关灯探房间对应 →lo/hi 游标

一人从门口向里、一人从窗边向外，各走各的，碰面即搜完

5第 5 页 · 单调性：循环变量的推进

基础划分的实现

python

Lomuto 划分的完整实现：一次遍历把小于等于轴点的元素推到左侧，最后把轴点安放到正确位置。

代码高亮加载中…

四个焦点对应不变性的两块拼图：i 维护「≤pivot 区」的右边界（不变性），j 的推进保证单调性，最后一步让轴点两侧天然有序于它。

6第 6 页 · 基础划分的实现

实例：一次完整划分

拿数组 [3,1,4,5,2] 以 2 为轴点，逐步验证不变式。

1
初始化
轴点取末尾的 2；i=-1，小于区为空，不变式平凡成立
2
扫描到 3
3 > 2，直接跳过，j 前进，大于区扩展为 [3]
3
扫描到 1
1 ≤ 2，i 变 0，交换后数组变 [1,3,4,5,2]
4
扫过 4 和 5
都大于 2，跳过；此时小于区=[1]，大于区=[3,4,5]
5
轴点归位
交换 i+1=1 与末尾，得 [1,2,4,5,3]，2 落在最终位置
7第 7 页 · 实例：一次完整划分

坏轴点如何拖垮快排

上一页的划分实例里，元素恰好被分得比较均匀。可如果轴点运气很差呢？每次划分都把数组切成「0 个和 n−1 个」，递归就会一路走到底。

一边倒的划分
已排序数组取首元素为轴点：划分结果是空 + 其余全部
递归深度变线性
每层只减少一个元素，深度从 log n 退化为 n
总比较次数
n + (n−1) + … + 1 ≈ n²/2，退化为 O(n²)
每次只挑走一个人对应 →一边倒划分

分队时一队全空，等于每次只确定一个人的位置

T(n)=T(n−1)+Θ(n) ⇒ T(n)=Θ(n2)T(n)=T(n-1)+\Theta(n)\ \Rightarrow\ T(n)=\Theta(n^2)
8第 8 页 · 坏轴点如何拖垮快排

变种之间的取舍对比

Lomuto 与 Hoare 划分最易混淆：交换次数、指针行为、最坏情况各不同，选错会让实现事倍功半。

Lomuto 划分
  • 单指针扫描，边界清晰易写
  • 交换次数多，约每元素一次
  • 全相等数组退化为 O(n²)
Hoare 划分
  • 双指针相向，写对要小心
  • 交换少，总交换约一半
  • 等值分布均匀，不易退化
教学或追求可读性时选 Lomuto；追求实际性能与抗退化选 Hoare，但必须逐行验证边界。
9第 9 页 · 变种之间的取舍对比

变种划分的实例推演

同一数组换成三数取中轴点，重走一遍划分，看结果差在哪。

1
选三个候选
取首 5、中 1、尾 2，三个位置比较大小
2
定中位数
中位数是 2，把它换到首位当轴点
3
跑划分
沿用同一套双向扫描，小于 2 在左，其余在右
4
对比结果
轴点 2 靠近最小端，两侧仍失衡——好策略也非银弹
10第 10 页 · 变种划分的实例推演

时间复杂度分析

上一页看到坏轴点拖垮快排，这一页把账算清楚：最好和最坏情形各写出递归式，再看三路划分与随机化如何把期望拉回 O(n log n)。

最好情形
轴点每次居中，T(n)=2T(n/2)+O(n)，解出 O(n log n)
最坏情形
轴点永远最值，T(n)=T(n-1)+O(n)，退化成 O(n²)
三路划分
等于轴点的段不再重复递归，大量重复元素时逼近 O(n)
随机化
随机选轴点，期望递归深度 O(log n)，期望 O(n log n)
切生日蛋糕对应 →递归划分

每刀切一半对应轴点居中；每刀只切下一小块对应退化

T(n)=T(k)+T(n−1−k)+O(n),k=0⇒O(n2), k=n/2⇒O(nlog⁡n)T(n)=T(k)+T(n-1-k)+O(n),\quad k=0 \Rightarrow O(n^2),\ k=n/2 \Rightarrow O(n\log n)
11第 11 页 · 时间复杂度分析

空间与稳定性

两个常被混为一谈的性质：栈空间取决于递归深度，稳定性取决于划分方式，二者成因完全不同。

递归栈空间
  • 最好 O(log n)：每次划分均衡
  • 最坏 O(n)：退化成链式递归
  • 尾递归优化可压到 O(log n)
稳定性
  • 稳定与否与递归深度无关
  • 划分时远距离交换破坏相对次序
  • 所有原地快排变种都不稳定
正确的理解是：空间是递归树的深度问题，能靠选轴和尾递归优化；不稳定是划分交换的固有代价，原地快排族改不掉。
12第 12 页 · 空间与稳定性

自测：不变性与退化

点击作答

快排退化到 O(n²) 的直接原因是什么？

13第 13 页 · 自测：不变性与退化

要点收束

  • ✓一切变种都靠同一条划分不变性立足
  • ✓循环变量单调推进是不变性成立的引擎
  • ✓划分写法千变，等价区间收缩本质不变
  • ✓坏轴点退化 O(n²) 是不变性的边界代价
  • ✓选变种先问：换来的代价值不值
延伸主题：三路划分处理重复元素随机化与中位数选轴策略内省排序：混合方案的工程实践
14第 14 页 · 要点收束

课后思考

先自己想十分钟，再对照参考答案——答案只是路径，不是终点。

1划分的循环不变式里，如果放宽「小于区与等于区分开」这一条，划分还正确吗？

参考答案提示：回看不变式页，等号归入哪一侧只影响边界位置；只要小于/大于两侧与轴点的关系不被破坏，最终递归仍正确，但交换次数可能变化。

2如果业务要求稳定排序，能否给快排打补丁补救？代价是什么？

参考答案方向：三路划分使相等元素集中，但跨区间交换仍打乱次序。可改为稳定划分（如链表版快排）或给元素附原始下标作决胜键，代价是额外空间与比较开销。

3「大量重复元素」是三路划分的主场，那「几乎有序」的输入该选哪个变种？

参考答案思路：几乎有序时坏轴点风险最高，随机化或三者取中轴点更对症；三路划分主要省重复元素的比较，对有序输入帮助有限。判断瓶颈在轴点质量还是元素分布。

15第 15 页 · 课后思考
(a4)快速排序：变种 · 知识图解