01先从一个问题出发
先让班级按一个人的身高分两组,再分别整理每组。
[4,2,5,3];pivot=3,boundary 从 0 开始。
归并先解决两半,快排先建立两半
归并先按位置平分,再排序并合并。快速排序先选 pivot,用大小关系分成两组:左边不大于 pivot,右边大于 pivot。把 pivot 放在中间后,它已处在升序结果中某个正确位置;左右组只需各自排序,不必再合并。
本课固定选择末尾元素,使用 Lomuto 分区。扫描时维护三段:a[left:boundary]≤pivot,a[boundary:j]>pivot,a[j:right] 尚未检查。pivot 暂时放在 right,不参加扫描。
遇到较小元素时,为什么和 boundary 交换
boundary 是『较小区间的下一个空位』。若 a[j]≤pivot,就把它放到 boundary,再令 boundary 加一。原来 boundary 上的较大值换到 j 后,仍位于扫描过的较大区间,不破坏规则。若 a[j]>pivot,只推进 j 即可。
扫描结束,把末尾 pivot 与 boundary 交换。左边全部≤pivot,右边全部>pivot,但左右内部未必有序。所以不能返回整个数组,仍要递归处理两边,并且不再把 pivot 包含进去。
02最直接的办法,为什么慢?
使用相邻交换反复扫描整个数组。
每次只能消除局部逆序,可能需要平方级比较。
03一步步,推导出优化思路
先确定一个基准的位置
先确定某个基准的最终位置,就能把大问题拆成互不干扰的两边。
维护较小区与较大区
boundary 左侧维护不大于基准的元素,扫描时按需交换。
排除基准,递归处理两侧
把基准放到 boundary,再递归排序左右区间。
扫描时 a[left:boundary] ≤ pivot,a[boundary:j] > pivot。
拿一个小输入,逐步手算
[4,2,5,3];pivot=3,boundary 从 0 开始。
| j / 当前值 | 判断 | 数组 | boundary |
|---|---|---|---|
| 0 / 4 | 4>3,不换 | [4,2,5,3] | 0 |
| 1 / 2 | 2≤3,换到 boundary | [2,4,5,3] | 1 |
| 2 / 5 | 5>3,不换 | [2,4,5,3] | 1 |
| 扫描完成 | pivot 与下标 1 交换 | [2,3,5,4] | pivot 就位于 1 |
| 递归右侧 | [5,4] 继续分区 | [2,3,4,5] | 完成 |
分区后的 [2,3,5,4] 不是完整排序结果。它只保证 3 两侧的大小关系,右边的 5、4 仍要处理。
分区不变量为什么保持
- 起初已扫描区间为空,较小区与较大区均为空,条件成立。
- 每读一项,把≤pivot 的项交换到较小区末端,或把>pivot 的项留在较大区;j 前进后所有已扫描项都有正确归属。
- pivot 放到边界后完成隔离。递归严格排除 pivot,使子区间缩小;长度≤1 时停止。左右排序后与 pivot 拼接得到整体有序。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
pivot, boundary = a[right], left- 这版使用闭区间 [left,right],与上一课的半开区间不同。先看约定再看边界,不能混抄。
for j in range(left, right):- 不扫描 right,因为那里保存 pivot。boundary 只在遇到较小值时前进,j 则每轮前进。
sort(left, boundary - 1)- 左边递归不含已经就位的 pivot;右边从 boundary+1 开始。
05复杂度,来自具体的工作量
分区平衡时递归深度 O(log n),每层 O(n)。本课固定末元素为基准,已排序或全相等输入可退化到 O(n²);平均复杂度依赖输入分布。
平衡递归栈 O(log n),最坏 O(n)。教学函数复制输入还需 O(n);工程中可随机化基准或三路分区。
把工作量具体数出来
一次分区线性扫描当前区间。若每次大致均分,O(log n) 层、每层 O(n),总计 O(n log n)。
固定末尾基准遇到升序 n 项,每次只确定最后一项:工作量为 (n−1)+(n−2)+…+1,最坏 O(n²)。全相等输入使用此分区也会严重不平衡。
递归栈平衡时 O(log n),最坏 O(n)。参考函数复制输入额外 O(n)。随机基准能改善期望表现,但不把最坏界变成保证;大量重复键可考虑三路分区。
06看到什么,应该想到它?
这些特征值得停下来想一想:
07这些细节,容易踩坑
固定基准可能退化
在逆序、已有序或大量相同值上观察分区不平衡。
不稳定
跨位置交换可能颠倒相等元素的次序。
名字叫快速,不代表每个输入都快
[1,2,3,4] 以末尾 4 为基准,左边有 3 项,右边为空;下一轮基准 3 又产生同样的不平衡。没有产生对半缩小。
怎样修正:把有序和全相等输入加入实验,观察递归深度。也要知道普通跨位置交换不稳定,例如 [2A,2B,1] 分区后可能成为 [1,2B,2A]。
08把想法带进真实题目
一次分区不必全部算完
对 [5,1,4,2] 做一次末尾基准分区。pivot 最后在哪?还要递归哪些区间?
需要一点提示
只有 1 不大于基准 2。
查看完整推导与答案
- 扫描到 1 时与 5 交换,数组变成 [1,5,4,2],boundary=1。
- 把 pivot=2 放到下标 1,得到 [1,2,4,5]。
- 递归 [0,0] 和 [2,3]。虽然右侧此时看起来有序,递归代码仍按规则验证它。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01分区后确定了哪个元素的位置?
02末尾基准遇到有序输入可能怎样?
03普通快速排序稳定吗?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。