一、算法结构
快速排序也是分治，但它把工作放在分解而非合并：
归并排序：轻分解（对半切）+ 重合并（Θ(n) 归并）
快速排序：重分解（Θ(n) 划分）+ 零合并（划分完就地有序）
QUICKSORT(A, lo, hi):
if lo < hi:
p = PARTITION(A, lo, hi) # 选一个主元，把 < 它的放左边，> 它的放右边
QUICKSORT(A, lo, p-1)
QUICKSORT(A, p+1, hi)
⭐ 划分之后主元已经在它最终的位置上，所以不需要合并——这就是"快速"的来源，也是它能原地排序的原因。
二、两种划分方案
Lomuto 划分（易写，易错在重复元素上）
// 以 a[hi] 为主元，返回主元最终位置
func lomutoPartition(a []int, lo, hi int) int {
pivot := a[hi]
i := lo - 1 // a[lo..i] 都 <= pivot
for j := lo; j < hi; j++ {
if a[j] <= pivot {
i++
a[i], a[j] = a[j], a[i]
}
}
a[i+1], a[hi] = a[hi], a[i+1]
return i + 1
}
循环不变式（第 1 讲）：
lo i j hi
┌─────────┬─────────┬────────────┬──────┐
│ ≤ pivot │ > pivot │ 未处理 │ pivot│
└─────────┴─────────┴────────────┴──────┘
⚠️ Lomuto 的致命弱点：全部元素相等时退化成 Θ(n²)。因为 a[j] <= pivot 恒成立，每次划分点都落在最右端，递归深度 n。这不是理论上的担忧——“某一列全是同一个值"在真实数据里非常常见。
Hoare 划分（更少交换，对重复元素更稳）
func hoarePartition(a []int, lo, hi int) int {
pivot := a[lo+(hi-lo)/2] // 取中间元素，避免有序输入的最坏情况
i, j := lo-1, hi+1
for {
for { i++; if a[i] >= pivot { break } }
for { j--; if a[j] <= pivot { break } }
if i >= j {
return j // ⚠️ 返回 j，且递归为 [lo,j] 与 [j+1,hi]（主元不一定在 j 处）
}
a[i], a[j] = a[j], a[i]
}
}
func QuickSort(a []int, lo, hi int) {
if lo >= hi { return }
p := hoarePartition(a, lo, hi)
QuickSort(a, lo, p)
QuickSort(a, p+1, hi)
}
| Lomuto | Hoare | |
|---|---|---|
| 交换次数 | 平均 n/2 | 平均 n/6，约少 3 倍 |
| 重复元素多时 | ✗ 退化 Θ(n²) | ✓ 两侧均匀切分 |
| 划分点语义 | 主元的最终位置 | 只是分界点，主元位置不定 |
| 代码陷阱 | 少 | 边界极易写错（i >= j 与递归区间必须配套） |
三、复杂度分析
递归式
最坏（每次划分出 0 和 n−1）： T(n) = T(n−1) + Θ(n) ⟹ Θ(n²)
最好（每次对半）： T(n) = 2T(n/2) + Θ(n) ⟹ Θ(n log n)
最坏情况何时发生？ 取 a[hi] 为主元时，已排序或逆序的输入就是最坏情况——而这恰恰是实践中最常见的输入之一。这是朴素快排的致命问题。
⭐ 关键洞察：只要分割比例是常数，就是 Θ(n log n)
假设每次划分都是最不平衡的 9:1：
T(n) = T(9n/10) + T(n/10) + Θ(n)
递归树（第 3 讲）：
n 代价 n
╱ ╲
n/10 9n/10 代价 n
╱ ╲ ╱ ╲
n/100 9n/100 9n/100 81n/100 代价 n
… ╲
最浅叶：log₁₀ n 最深叶：log_{10/9} n ≈ 6.6 log₁₀ n
每一层的总代价仍是 ≤ n，层数在 log₁₀ n 与 log_{10/9} n 之间——都是 Θ(log n)，只差常数。所以
T(n) = Θ(n log n)
⭐ 这是本讲最重要的结论：快排不需要"完美对半”，只需要"不要每次都切出空的一半"。 9:1 的分割只比对半分割慢约 3 倍（常数），而不是差一个量级。
直觉：好划分与坏划分交替也无妨
假设最坏与最好交替出现：
T(n) = T(n−1) + Θ(n) （坏划分）
T(n−1) = 2T((n−1)/2) + Θ(n) （好划分）
⟹ T(n) = 2T(n/2) + Θ(n) = Θ(n log n)
一次坏划分的代价被下一次好划分吸收了。 快排对偶发的坏运气极其鲁棒——它怕的只有系统性的坏输入。
四、随机化：把最坏情况变成小概率事件
问题的根源：主元的选择是确定性的，攻击者或不巧的数据分布可以构造最坏输入。
解法（与第 7 讲全域散列完全相同的思路）：让随机性来自算法自己。
func randomizedPartition(a []int, lo, hi int) int {
r := lo + rand.IntN(hi-lo+1)
a[r], a[hi] = a[hi], a[r] // 随机主元换到末尾，其余同 Lomuto
return lomutoPartition(a, lo, hi)
}
关键性质：期望运行时间不依赖输入。没有任何一个输入能让随机化快排系统性地变慢——对每个固定输入，慢的概率都极低。这正是第 4 讲中"期望"与"平均情况"的区别。
⭐ 期望 O(n log n) 的证明
观察：快排的全部代价由比较次数支配。设排序后的数组为 z₁ < z₂ < … < zₙ。
定义指示随机变量：
X_{ij} = 1，当且仅当 zᵢ 与 zⱼ 在整个算法过程中被比较过
总比较次数 X = Σ_{i<j} X_{ij}，故 E[X] = Σ_{i<j} Pr[zᵢ 与 zⱼ 被比较]。
核心引理：zᵢ 与 zⱼ 被比较，当且仅当 zᵢ 或 zⱼ 是集合 Zᵢⱼ = {zᵢ, zᵢ₊₁, …, zⱼ} 中第一个被选为主元的元素。
为什么？
- 若 Zᵢⱼ 中先被选中的是某个中间元素 z_k（i < k < j），则 zᵢ 和 zⱼ 被分到划分的两侧，此后再无机会相遇 ⟹ 永不比较。
- 若先被选中的是 zᵢ（或 zⱼ），它作为主元要与当前子数组的所有元素比较，包括 zⱼ ⟹ 比较恰好一次。
- 两个元素至多被比较一次（主元比较完就被移出递归）。
由于主元是从当前子数组中均匀随机选取的，Zᵢⱼ 中每个元素等概率成为第一个主元，|Zᵢⱼ| = j − i + 1：
Pr[zᵢ 与 zⱼ 被比较] = 2 / (j − i + 1)
于是
E[X] = Σ_{i=1}^{n-1} Σ_{j=i+1}^{n} 2/(j−i+1)
= Σ_{i=1}^{n-1} Σ_{k=1}^{n-i} 2/(k+1) （令 k = j−i）
< Σ_{i=1}^{n-1} Σ_{k=1}^{n} 2/k
= Σ_{i=1}^{n-1} 2·Hₙ
= O(n log n) ∎
（用到 Hₙ = Θ(log n)，第 2 讲。）
⭐ 精确常数：期望比较次数约为 1.39 n log₂ n，即比信息论下界（第 12 讲）只多 39%。
尾概率：可以进一步证明，随机化快排耗时超过 c·n log n 的概率随 c 指数下降。n = 10⁶ 时退化到 Θ(n²) 的概率比硬件故障率还低得多。
五、重复元素：三路划分
问题：数组中只有少数几个不同的值（如按状态码、性别、布尔标志排序）。二路划分下相等元素被反复递归，退化到 Θ(n²)。
Dijkstra 的荷兰国旗划分把数组分成三段：
lo lt i gt hi
┌──────────┬───────────┬───────────┬──────────┐
│ < pivot │ == pivot │ 未处理 │ > pivot │
└──────────┴───────────┴───────────┴──────────┘
func QuickSort3Way(a []int, lo, hi int) {
if lo >= hi {
return
}
r := lo + rand.IntN(hi-lo+1)
a[lo], a[r] = a[r], a[lo]
pivot := a[lo]
lt, i, gt := lo, lo+1, hi
for i <= gt {
switch {
case a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt++; i++
case a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt-- // 注意 i 不前进：换过来的元素还没检查
default:
i++
}
}
QuickSort3Way(a, lo, lt-1)
QuickSort3Way(a, gt+1, hi) // ⭐ 等于 pivot 的整段不再递归
}
⭐ 等于主元的整段直接跳过递归。若数组只有 k 个不同值，复杂度变成 Θ(n log k)；全部相同时是 Θ(n)。
六、工程加固：Go 的 pdqsort
slices.Sort / sort.Slice 在 Go 1.19 后使用 pdqsort（pattern-defeating quicksort）。它是快排 + 一系列针对已知失败模式的补丁：
| 措施 | 解决什么问题 |
|---|---|
| 小数组切插入排序（n ≤ 12） | 递归常数开销 > n² 与 n log n 的差距 |
| 中位数选主元：n 小用三数取中，n 大用 ninther（九数取中） | 降低坏划分概率 |
| 递归深度超 2⌊log n⌋ 切堆排序（introsort 兜底） | 把最坏情况从 Θ(n²) 压到 Θ(n log n) |
| 检测已排序 / 已逆序的模式 | 常见输入上做到接近 Θ(n) |
| 划分极不平衡时打乱几个元素 | 打破对抗性输入的构造 |
| 相等元素多时切三路划分 | 重复元素退化 |
| 只递归较小的一半，较大的一半用尾循环 | 栈深度从 O(n) 降到 O(log n) |
最后一条值得单独说明：
func quickSortTailCall(a []int, lo, hi int) {
for lo < hi {
p := partition(a, lo, hi)
if p-lo < hi-p { // 先递归较小的一半
quickSortTailCall(a, lo, p-1)
lo = p + 1 // 较大的一半用循环代替递归
} else {
quickSortTailCall(a, p+1, hi)
hi = p - 1
}
}
}
每次递归的规模至少减半 ⟹ 递归深度 ≤ log₂ n，即使划分一直很糟糕也不会爆栈。
七、三大 Θ(n log n) 排序对比
| 快速排序 | 归并排序 | 堆排序 | |
|---|---|---|---|
| 平均 | Θ(n log n)，常数最小 | Θ(n log n) | Θ(n log n) |
| 最坏 | Θ(n²)（随机化后概率极低） | Θ(n log n) | Θ(n log n) |
| 额外空间 | O(log n)（递归栈） | Θ(n) | O(1) |
| 稳定 | ✗ | ✓ | ✗ |
| 缓存局部性 | 最优（顺序扫描） | 良 | 差（跳跃访问） |
| 并行 | 好 | 最好 | 差 |
| 典型使用者 | Go slices.Sort、C qsort、Rust sort_unstable |
Go SortStable、Python/Java 对象排序（Timsort） |
introsort 的兜底 |
⭐ 快排在实践中通常最快，原因不在渐近复杂度，而在于它对内存的访问模式：划分是两个方向的顺序扫描，硬件预取器可以完美预测。这是第 2 讲和第 5 讲反复强调的那件事——同一个 Θ(n log n) 里，常数由缓存决定。
随堂自测
- 为什么快速排序不需要"合并"步骤？这与归并排序的工作分配有什么本质不同？
- Lomuto 划分在"所有元素相等"时会发生什么？Hoare 划分为什么没有这个问题？
- 证明：若每次划分比例固定为 1:99，快排仍是 Θ(n log n)。给出层数的上下界。
- 用指示随机变量证明随机化快排的期望比较次数是 O(n log n)。写出关键引理及其证明。
- 为什么
Pr[zᵢ 与 zⱼ 被比较] = 2/(j−i+1)？为什么相邻的两个元素几乎一定会被比较，而最小与最大几乎一定不会？ - 三路划分在什么输入上把 Θ(n log n) 降到 Θ(n)？给出复杂度关于"不同值个数 k"的表达式。
- “只递归较小的一半"如何把栈深度从 O(n) 降到 O(log n)？
- 随机化快排的最坏情况仍是 Θ(n²)，为什么工程上可以接受？如果不能接受（如硬实时系统），该怎么办？
- 排序 1000 万条记录、必须稳定、内存充足，你选哪个算法？如果内存只有输入大小的 1.1 倍呢？