引言
快速排序（Quicksort）由 Tony Hoare 于 1959 年提出，是最经典的分治算法之一。其核心思想可以用一句话概括：
选择一个 pivot，将数组划分为"小于 pivot"和"大于 pivot"两部分，然后递归处理子数组。
这篇文章将从数学原理出发，结合 Python 实现，逐步深入工程中的优化技巧。
数学基础：渐进复杂度分析
快速排序的时间复杂度依赖于划分是否均匀。设 $T(n)$ 为对长度为 $n$ 的数组排序的期望时间，则有递推式：
$$ T(n) = \frac{1}{n} \sum_{k=0}^{n-1} \big[T(k) + T(n-k-1)\big] + \Theta(n) $$
解此递推式可得期望时间复杂度为 $\Theta(n \log n)$。我们可以用积分近似来验证：
$$ \int_{1}^{n} x \ln x , dx \approx \frac{n^2 \ln n}{2} - \frac{n^2}{4} $$
而最坏情况下，每次划分都极不均匀（例如已排序数组且总是选首元素为 pivot），退化至：
$$ T(n) = T(n-1) + \Theta(n) \implies T(n) = \Theta(n^2) $$
空间复杂度
递归调用栈的深度在最好情况下为 $O(\log n)$，最坏情况下为 $O(n)$。通过尾递归优化可以将最坏空间降至 $O(\log n)$。
算法实现
基础版本：Lomuto 划分
1def quicksort_lomuto(arr: list[int], low: int, high: int) -> None:
2 """Lomuto partition scheme — 简单直观但交换次数较多"""
3 if low >= high:
4 return
5
6 pivot = arr[high] # 选最后一个元素作为 pivot
7 i = low - 1 # i 指向"小于 pivot 的区域"的末尾
8
9 for j in range(low, high):
10 if arr[j] < pivot:
11 i += 1
12 arr[i], arr[j] = arr[j], arr[i]
13
14 i += 1
15 arr[i], arr[high] = arr[high], arr[i] # 将 pivot 放到正确位置
16
17 quicksort_lomuto(arr, low, i - 1)
18 quicksort_lomuto(arr, i + 1, high)
在 Python 中，还可以用更简洁的列表推导式：
1def quicksort_pythonic(arr: list[int]) -> list[int]:
2 """Functional-style quicksort — NOT in-place"""
3 if len(arr) <= 1:
4 return arr
5 pivot = arr[len(arr) // 2]
6 left = [x for x in arr if x < pivot]
7 mid = [x for x in arr if x == pivot]
8 right = [x for x in arr if x > pivot]
9 return quicksort_pythonic(left) + mid + quicksort_pythonic(right)
工程优化版本：三路划分 + 插入排序混合
1// 三路划分 (Three-way Partition) —— 适合大量重复元素
2void quicksort_3way(int arr[], int low, int high) {
3 if (low >= high) return;
4
5 // 小数组切换到插入排序
6 if (high - low < 16) {
7 insertion_sort(arr + low, high - low + 1);
8 return;
9 }
10
11 int lt = low, gt = high;
12 int pivot = arr[low];
13 int i = low;
14
15 while (i <= gt) {
16 if (arr[i] < pivot) swap(arr + lt++, arr + i++);
17 else if (arr[i] > pivot) swap(arr + i, arr + gt--);
18 else i++;
19 }
20
21 quicksort_3way(arr, low, lt - 1);
22 quicksort_3way(arr, gt + 1, high);
23}
不同划分策略对比
| 策略 | pivot 选择 | 最坏时间 | 额外空间 | 重复元素处理 |
|---|---|---|---|---|
| Lomuto | 固定末尾 | $O(n^2)$ | $O(1)$ | 差 |
| Hoare | 固定中间 | $O(n^2)$ | $O(1)$ | 一般 |
| 三路划分 | 固定首元素 | $O(n^2)$ | $O(1)$ | 优秀 |
| IntroSort | 三数取中 | $O(n \log n)$ | $O(\log n)$ | 良好 |
| PDQSort | 多种启发式 | $O(n \log n)$ | $O(\log n)$ | 极佳 |
备注：Rust 标准库的
slice::sort_unstable使用 PDQSort（Pattern-Defeating Quicksort），它在检测到"过于有序"时会自动切换为堆排序。
性能基准测试
使用 Go 的 testing 包对一百万条随机记录进行基准测试：
1func BenchmarkQuicksort(b *testing.B) {
2 data := make([]int, 1_000_000)
3 for i := range data {
4 data[i] = rand.Intn(1_000_000)
5 }
6 b.ResetTimer()
7 for i := 0; i < b.N; i++ {
8 copy := append([]int(nil), data...)
9 quicksort(copy)
10 }
11}
12// BenchmarkQuicksort-16 4 286 ms/op
图：快速排序动画演示 (来源: Wikipedia)
实际应用场景
下表总结了不同语言/库中快速排序的使用情况：
| 语言 / 库 | 排序函数 | 底层算法 | 是否稳定 |
|---|---|---|---|
C++ std::sort | std::sort | Introsort | ✗ |
| Rust | slice::sort_unstable | PDQSort | ✗ |
| Python | list.sort() | Timsort (归并 + 插入) | ✓ |
Java Arrays.sort (基本类型) | Dual-Pivot Quicksort | 双轴快排 | ✗ |
| Go | sort.Slice | PDQSort (≥1.21) | ✗ |
| JavaScript V8 | Array.prototype.sort | Timsort | ✓ |
小结
在这篇文章中，我们涵盖了：
- 快速排序的递推式 $T(n)$ 及其数学分析
- 三种不同风格的代码实现：
Lomuto、Pythonic、三路划分 C - 不同 pivot 选择策略的性能对比
- 各主流语言标准库的排序算法选择
关键结论：快速排序仍是大多数标准库的首选通用排序，但几乎都加入了混合策略来避免最坏情况。
本文共计约 2000 字，适合有一定算法基础的读者。如有疑问欢迎在评论区讨论。