快速排序
快速排序按基准值把区间划分成小于、等于和大于三段，再递归处理两侧；二路划分作为经典变体补充。
一句话算法
选一个基准值，把小的放左边、相等的集中在中间、大的放右边，然后只递归中间段的两侧。
问题模型
给定一个长度为
快速排序要解决的核心子问题是：
如何在线性时间内，把区间
[l,r]按基准值key划分成几个更容易处理的连续部分？
本文先学习三路划分。一次划分结束后，区间变成：
< key | == key | > key
中间段已经有序，不需要再次处理；递归排序左右两段即可。二路划分会把等于基准值的元素留在两侧，代码更短，但边界更难记，放在后文作为经典变体。
三路版本
三路快速排序是本文推荐的手写版本。它把等于基准值的元素一次集中起来，尤其适合含有大量重复元素的数组。
荷兰国旗模型
把小于、等于、大于 key 的元素看成三种颜色。扫描数组时，每看到一个元素，就把它送入对应的颜色区域：
< key | == key | 尚未检查 | > key
扫描完成后，“尚未检查”区域消失：
< key | == key | > key
等于 key 的整段不需要递归，这是三路划分处理重复元素的关键。
区间不变量
扫描过程中，三个指针 lt、i、gt 把 [l,r] 分成四段：
[l, lt-1] | [lt, i-1] | [i, gt] | [gt+1, r]
< key | == key | 未检查 | > key
这四段的含义始终不变：
[l,lt-1]中的元素都小于key。[lt,i-1]中的元素都等于key。[i,gt]中的元素还没有检查。[gt+1,r]中的元素都大于key。
只要记住“i 指向当前元素，[i,gt] 还没有检查”，三个分支的移动方式就能自然推出。
下面用格子画出当前状态。每个 +---+ 格子表示一个元素，? 表示这个元素还没有分类。
lt i gt
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | = | = | ? | ? | ? | > | > |
+---+---+---+---+---+---+---+---+---+
三种情况为什么保持不变量
情况一：a[i] < key
操作前，i 指向一个小于 key 的元素：
lt i gt
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | = | = | < | ? | ? | > | > |
+---+---+---+---+---+---+---+---+---+
执行：
1
2
3
swap(a[i], a[lt]);
lt++;
i++;
操作后：
lt i gt
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | < | = | = | ? | ? | > | > |
+---+---+---+---+---+---+---+---+---+
小元素进入左段，原来位于 lt 的 key 被换到等于段末尾；lt、i 同时右移后，四段定义恢复。
情况二：a[i] == key
操作前，i 指向一个等于 key 的元素：
lt i gt
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | = | = | = | ? | ? | > | > |
+---+---+---+---+---+---+---+---+---+
不需要交换，只执行 i++。操作后：
lt i gt
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | = | = | = | ? | ? | > | > |
+---+---+---+---+---+---+---+---+---+
数组内容没有变化，i 右移后，当前元素被并入等于段，四段定义恢复。
情况三：a[i] > key
操作前，i 指向一个大于 key 的元素：
lt i gt
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | = | = | > | ? | ? | > | > |
+---+---+---+---+---+---+---+---+---+
执行：
1
2
swap(a[i], a[gt]);
gt--;
操作后：
lt i gt
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | = | = | ? | ? | > | > | > |
+---+---+---+---+---+---+---+---+---+
大元素进入右段，但从 gt 换到 i 的元素还没有分类，所以 i 不能移动；gt 左移后，四段定义恢复。
什么时候停止
未检查区 [i,gt] 的元素个数是：
三个分支每次都让它恰好减少 1：
a[i]<key：i++。a[i]==key：i++。a[i]>key：gt--。
未检查区的长度不可能无限减小，因此循环一定停止。循环条件是 i<=gt，第一次不满足条件时必有 i=gt+1：
lt gt i
| | |
v v v
+---+---+---+---+---+---+---+---+---+
| < | < | = | = | = | > | > | > | > |
+---+---+---+---+---+---+---+---+---+
此时 [i,gt] 是空区间，四段合并成最终的三段：
[l,lt-1]中的元素都小于key。[lt,gt]中的元素都等于key。[gt+1,r]中的元素都大于key。
完整流程
- 若区间长度小于等于
1，直接返回。 - 随机选择一个基准元素，把它交换到
a[l]，并保存基准值key。 - 初始化
lt=l、i=l+1、gt=r。此时a[l]单独构成等于区。 - 当
i<=gt时，按照上面的三种情况处理a[i]，不断缩短未检查区。 - 当
i=gt+1时扫描结束，递归排序[l,lt-1]与[gt+1,r]。
正确性
初始时，[l,lt-1] 和 [gt+1,r] 都是空区间，[lt,i-1]=[l,l] 中只有基准元素，因此四段不变量成立。上面的分类讨论已经证明，每次循环后不变量仍然成立。
循环停止时未检查区为空，所以整个区间被正确划分成“小于、等于、大于”三段。
等于段不需要递归。左右两段都比原区间短，对它们递归执行相同操作；长度为 0 或 1 时天然有序，因此整个区间最终有序。
复杂度
设当前区间长度为
- 随机选择基准时，期望时间复杂度为
。 - 基准值连续落在极端位置时，最坏时间复杂度为
。 - 除递归栈外只使用常数个变量；递归栈期望为
，最坏为 。 - 当所有元素都相等时，只需一次
的划分，不会继续递归。
动画
动画只展示一次划分。观察 lt、i、gt 的移动，并把它们与四段不变量对应起来。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int a[maxn];
int n;
// 三路快速排序 3-Way Quick Sort
void quick_sort(int l, int r) {
if (l >= r) return;
// 1. 随机选一个基准数 (防止被针对卡成 O(N^2))
// 也可以简单写成 int key = a[(l+r)/2];
int rand_idx = l + rand() % (r - l + 1);
swap(a[l], a[rand_idx]);
int key = a[l]; // 选取 a[l] 作为 key，并以此展开
// 2. 定义指针
int lt = l; // lt (less than) : 指向 "等于区" 的第一个位置
int gt = r; // gt (greater than): 指向 "等于区" 的最后一个位置
int i = l + 1; // i : 当前扫描到的位置 (从 l+1 开始，因为 a[l] 是 key)
// 3. 扫描并分类
while (i <= gt) {
if (a[i] < key) {
// 情况A: 发现比 key 小的，扔到左边 (lt)
// 把 a[i] 和 a[lt] 交换，然后 lt 和 i 都右移
swap(a[i], a[lt]);
lt++;
i++;
}
else if (a[i] > key) {
// 情况B: 发现比 key 大的，扔到右边 (gt)
// 把 a[i] 和 a[gt] 交换，gt 左移
// 注意：i 不能动！因为从 gt 换回来的数还没检查过
swap(a[i], a[gt]);
gt--;
}
else {
// 情况C: 等于 key，直接跳过，i 右移
i++;
}
}
// 此时数组状态：
// [l ... lt-1] 都是 < key
// [lt ... gt] 都是 == key (这一段已经排好了，不需要递归！)
// [gt+1 ... r] 都是 > key
// 4. 递归处理左右两边
quick_sort(l, lt - 1);
quick_sort(gt + 1, r);
}
int main() {
// 基础输入输出优化
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
// 种子随机数，防止被黑客数据卡死
srand(time(0));
quick_sort(1, n);
for(int i = 1; i <= n; ++i) cout << a[i] << (i == n ? "" : " ");
cout << "\n";
return 0;
}
二路版本
二路快速排序把区间分成“不大于 key”和“不小于 key”两部分。等于 key 的元素可以出现在任意一边，因此左右两段都要继续递归。
双指针模型
左指针 i 从左向右找放错侧的元素，右指针 j 从右向左找放错侧的元素：
<= key | 尚未检查 | >= key
i ... j
找到一对元素后交换它们，再继续向中间扫描。两个指针交错时，一次划分结束。
操作步骤
- 若区间长度小于等于
1，直接返回。 - 取区间中间位置的值作为
key，初始化i=l、j=r。 - 当
a[i]<key时，令i++，跳过已经在正确侧的元素。 - 当
a[j]>key时，令j--，跳过已经在正确侧的元素。 - 若
i<=j，交换a[i]与a[j]，然后令i++、j--。 - 重复扫描，直到
i>j。 - 递归排序
[l,j]与[i,r]。
边界与递归
二路版本难记的地方不在交换，而在下面三个边界：
- 内层扫描必须使用
<key和>key。遇到等于key的元素时要停下，否则重复元素可能被直接越过。 - 交换后必须同时执行
i++和j--。如果两端都等于key而指针不动，循环就不会结束。 - 递归区间是
[l,j]与[i,r]。key只是一个保存下来的值，不代表某个元素最终固定在原来的中点位置。
这也是本文把二路版本放在三路版本之后的原因：代码较短，但正确书写依赖更多边界约定。
正确性
扫描过程中保持下面的不变量：
[l,i-1]中已经检查过的元素都不大于key。[j+1,r]中已经检查过的元素都不小于key。[i,j]是尚未完成划分的部分。
指针移动只会跳过已经在正确侧的元素；交换则把左侧的较大元素和右侧的较小元素同时送回正确侧。因此指针交错后，左段 [l,j] 中的元素都不大于 key，右段 [i,r] 中的元素都不小于 key。
每次交换后两个指针都会向中间移动，递归区间也严格缩短。递归排序左右两段后，整个区间有序。
复杂度
一次二路划分的时间复杂度为
- 平均时间复杂度为
。 - 最坏时间复杂度为
。 - 递归栈平均为
，最坏为 。
与三路版本相比，二路版本不会一次排除所有等于 key 的元素。重复元素很多时，三路版本通常需要处理的递归区间更小。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn];
int n;
void quick_sort(int l, int r) {
// 1. 递归出口：如果区间只有一个数或没有数，直接返回
if (l >= r) return;
// 2. 选取基准数 (Pivot)
// 建议取中间的数，防止在原本有序的数组上退化成 O(N^2)
int mid = a[(l + r) / 2];
// 定义双指针
int i = l, j = r;
// 3. Partition 分区操作
// 目标：让左边 [l, j] 所有的数 <= mid
// 让右边 [i, r] 所有的数 >= mid
while (i <= j) {
// 左指针向右找，直到找到一个 >= mid 的数停下
// 注意：这里必须是 < mid，不能是 <=。遇到等于 mid 的也要停下，
// 这样可以将重复的 mid 均匀分散到两边，避免树倾斜。
while (a[i] < mid) i++;
// 右指针向左找，直到找到一个 <= mid 的数停下
while (a[j] > mid) j--;
// 如果指针没有交错，说明找到了一对“放错位置”的数，交换它们
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
// 4. 递归处理子区间
// 此时指针已经“错车”了：j 在左边，i 在右边 (j < i)
// 分割点变成了 j 和 i
// 递归处理左半段 [l ... j]
if (l < j) quick_sort(l, j);
// 递归处理右半段 [i ... r]
if (i < r) quick_sort(i, r);
}
int main() {
// 读写加速
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
quick_sort(1, n);
for (int i = 1; i <= n; ++i) cout << a[i] << " ";
cout << endl;
return 0;
}
划分思想的扩展
如果只求第
一次划分后，第
- 落在等于段，答案已经找到。
- 落在左段，只递归左段。
- 落在右段，只递归右段。
这就是快速选择。随机选择基准时，它的期望时间复杂度为
经典例题
-
luogu-P1177 排序模板题。可以用本文任一版本理解完整的快速排序过程；实际竞赛中通常优先使用
std::sort。 -
luogu-P1923 求第
小。利用三路划分判断答案落在哪一段，每次只保留一个递归方向。