快速排序

2026 大纲 七（七）快速排序。

一趟划分：让一个元素直接到达最终位置

冒泡排序的一次交换只消除一个逆序对，所以它慢。快速排序改的就是这一点：一次交换跨越很远，一口气消除多个逆序对。

具体做法是划分（Partition）：挑一个元素当枢轴，扫一遍把比它小的都甩到左边、比它大的都甩到右边，于是

枢轴到达最终位置，左边全 $\leq$ 它、右边全 $\geq$ 它。 然后对左右两个子表递归。

这就带出它最重要的一个指纹：

🔴 枢轴不一定是极值。 冒泡和选择每趟归位的都是当前区间的全局最值，而快排归位的是一个分界元素——它可能在数组中间任何位置。判断中间状态时看的是"左小右大的分界点"，不是"某端聚集了最值"。

先动手看一眼

加载可视化中...

代码与三处不能改的地方

void QuickSort(int A[], int low, int high) {
    if (low < high) {                            // 出口：子表长度 ≤ 1 天然有序
        int pivotPos = Partition(A, low, high);
        QuickSort(A, low, pivotPos - 1);         // 递归调用不含 pivotPos 本身，
        QuickSort(A, pivotPos + 1, high);        // 漏掉 ∓1 会无限递归
    }
}

// 挖坑法：枢轴暂存腾出一个"坑"，两端交替扫描，找到该换到对面去的就填进坑里
int Partition(int A[], int low, int high) {
    int pivot = A[low];                 // A[low] 成为第一个坑
    while (low < high) {
        while (low < high && A[high] >= pivot)
            high--;                     // 从右往左找第一个 < pivot 的
        A[low] = A[high];               // 填进左边的坑，A[high] 成为新坑
        while (low < high && A[low] <= pivot)
            low++;                      // 从左往右找第一个 > pivot 的
        A[high] = A[low];
    }
    A[low] = pivot;                     // low == high，枢轴填进最后一个坑
    return low;
}

第一，>= / <= 不能写成 > / <。 序列中有与枢轴相等的元素时，两个内层循环都会停在它那里不动指针，外层 while 空转——死循环。反例 A = [5, 5]：用 > 时 5 > 5 为假 high 不动，填坑后 5 < 5 为假 low 也不动。

第二，内层循环的 low < high 不能省，否则指针越过对方、读到区间外。

第三，必须先扫 high 再扫 low（枢轴取自 A[low] 时）——第一个坑在左端，只有从右边找小元素来填才不会覆盖有效数据。枢轴取自 A[high] 则次序反过来。

存储结构：排序过程要反复定位子表的上下界、还要双向扫描，所以适合顺序表、难用于链表。

最怕的输入，正好是别人最喜欢的

这是快排最反直觉、也最常被考的一条：

🔴 初始序列已有序（正序或逆序）+ 取首元素为枢轴 = 最坏情况 $O (n^{2})$ 。

道理很直接：

正序输入：A[low] 是最小值，右扫描找不到更小的，high 一路减到 low，左子表为空；
逆序输入：A[low] 是最大值，右扫描第一步就停，左子表拿到 $n - 1$ 个。

两种情况下递归树都退化成单支链，深度 $n - 1$ ，比较次数

{KCN}_{max} = \sum_{i = 1}^{n - 1} (n - i) = \frac{n (n - 1)}{2}

对比一下就看出差别在哪：直接插入和冒泡在有序输入上最快（逆序对为 0），快排偏偏在有序输入上最慢。

🔴 快排的效率取决于"划分是否均匀"，与逆序对多少完全无关。 记住这一句，这类判断题就不会错。

最好情况是每次均分，递归树高 $\log_{2} n$ 、每层所有子表长度加起来是 $O (n)$ ，故 $O (n \log_{2} n)$ ；平均情况也是 $O (n \log_{2} n)$ ，而且平均意义下它是所有内部排序里最快的——内层循环只做一次比较加一次赋值，且从两端顺序扫描，对缓存友好。

空间是递归栈，不是 $O (1)$

🔴 不用辅助数组 $\neq$ 不用空间。 快排的空间开销全部来自递归栈，等于递归树的深度：最好 $O (\log_{2} n)$ 、平均 $O (\log_{2} n)$ 、最坏 $O (n)$ 。

说快排空间 $O (1)$ 是错的，真题把"要求空间复杂度为 $O (1)$ "作为"该用直接插入排序而不该用快排"的正当理由考过。

由此还牵出一个常被问的细节：先处理长分区还是短分区，会不会影响递归次数？

不影响递归次数，只影响栈深度。 划分结果一旦确定，左右两边的递归调用都必然发生，总调用次数由划分结果唯一决定，与处理顺序无关。变的是最大栈深：先处理短分区可以把栈深压到 $O (\log n)$ （长的那半留在循环里迭代处理），先处理长分区最坏可达 $O (n)$ 。

⚠️ 而递归次数与初始排列大有关系（最好 $O (n \log n)$ 、最坏 $O (n^{2})$ ），别把这两句话搞混。

判"某序列能不能是第 $k$ 趟结果"

这是快排最常出现的题型，判据只有一条：

🔴 第 $k$ 趟结束时，至少有 $k$ 个元素已经"就位"，而一个元素就位的标志是：它左边的全部 $\leq$ 它，右边的全部 $\geq$ 它。

所以做法是：逐个扫描序列，找出所有满足"左边全小、右边全大"的元素，数一数有几个。

第 1 趟结果至少有 1 个这样的元素；
第 2 趟结果至少有 2 个（原枢轴 + 左右子表各自的新枢轴里至少一个……实际至少 2 个，最多 3 个）；
第 $k$ 趟累计就位的元素个数在 $[k, 2^{k} - 1]$ 之间。

手法：从左往右扫一遍记录前缀最大值，从右往左扫一遍记录后缀最小值；某个位置若"前缀最大值 = 自己"且"后缀最小值 = 自己"，它就已就位。四个选项里数不够 $k$ 个的那个就是答案。

由一次划分结果反推枢轴也是同一条判据的应用：给一个"经过一次划分后"的序列问枢轴是哪个，就是找那个唯一满足"左边全 $\leq$ 它、右边全 $\geq$ 它"的元素。

⚠️ 另一个要说准的点：一趟划分后，两部分只是"块间有序"，块内仍然是乱的。真题问过"第一趟把除枢轴外的 $N - 1$ 个元素划分为 $P$ 、 $Q$ 两部分，下列叙述正确的是"——正确的是" $P$ 和 $Q$ 块间有序"；而"块内有序"（还没排）、"元素个数大致相等"（取决于枢轴）、"不存在相等元素"（毫无根据）都是错的。

一趟划分的逐步推演（第一次学、或想手动模拟时展开）

对 {49, 38, 65, 97, 76, 13, 27, 49*} 用挖坑法，pivot = A[0] = 49：

步	low	high	动作	数组状态（`_` 是当前的坑）
0	0	7	`pivot = 49` 暂存	`_ 38 65 97 76 13 27 49*`
1	0	7	`A[7]=49* >= 49`，`high--`	`_ 38 65 97 76 13 27 49*`
2	0	6	`A[6]=27 < 49` 停；`A[0]=A[6]`	`27 38 65 97 76 13 _ 49*`
3	0→2	6	`27`、`38` 都 $\leq 49$ 故 `low++`；`A[2]=65 > 49` 停	`27 38 65 97 76 13 _ 49*`
4	2	6	`A[6]=A[2]`	`27 38 _ 97 76 13 65 49*`
5	2	5	`A[5]=13 < 49` 停；`A[2]=A[5]`	`27 38 13 97 76 _ 65 49*`
6	3	5	`A[3]=97 > 49` 停；`A[5]=A[3]`	`27 38 13 _ 76 97 65 49*`
7	3	5→3	`97`、`76` 都 $\geq 49$ 故 `high--`，`low == high == 3`	`27 38 13 _ 76 97 65 49*`
8	3	3	外层退出，`A[3] = pivot`	`27 38 13 49 76 97 65 49*`

整个排序过程：

趟（递归层）	本层子表	新归位	全表状态
初始	—	—	49 38 65 97 76 13 27 49*
第 1 趟	`[0,7]`	49	27 38 13 49 76 97 65 49*
第 2 趟	`[0,2]`、`[4,7]`	27、76	13 27 38 49 49* 65 76 97
第 3 趟	`[0,0]`、`[2,2]`、`[4,5]`、`[7,7]`	49*	13 27 38 49 49* 65 76 97

另一种划分写法：两端交换法（题目给了这种代码时展开）

两个指针分别停在"该去右边的"和"该去左边的"元素上，直接交换这两个，最后枢轴与分界处交换：

int Partition2(int A[], int low, int high) {
    int pivot = A[low], i = low, j = high;
    while (i < j) {
        while (i < j && A[j] >= pivot) j--;
        while (i < j && A[i] <= pivot) i++;
        if (i < j) { int t = A[i]; A[i] = A[j]; A[j] = t; }
    }
    int t = A[low]; A[low] = A[i]; A[i] = t;
    return i;
}

两种写法都正确，但划分后的具体排列不同，枢轴位置通常相同。以 {49,38,65,97,76,13,27,49*} 为例：

写法	一趟结果	枢轴位置
挖坑法	`27 38 13 [49] 76 97 65 49*`	下标 3
两端交换法	`13 38 27 [49] 76 97 65 49*`	下标 3

按题目给的代码走；没给就按挖坑法（教材算法 8.5）。不要把两种写法的中间状态混着用。

复杂度的完整推导

最好：每次均分，划分本身约 $n$ 次比较，之后是两个 $n / 2$ 的子问题：

T (n) = C n + 2 T (n / 2)

逐层展开 $T (n) \leq k n + 2^{k} T (n / 2^{k})$ ，当 $2^{k} = n$ 即 $k = \log_{2} n$ 时递归到底，得 $O (n \log_{2} n)$ 。

空间：最大递归层数 = 递归树深度。最好 $⌈ \log_{2} (n + 1) ⌉$ 、平均 $O (\log_{2} n)$ （实测 $n = 1023$ 时约 $2 \log_{2} n$ ）、最坏 $n$ 。工程上常"每层先递归较短一侧、较长一侧改用循环"，可把栈深压到 $O (\log_{2} n)$ 。

指标	最好	平均	最坏
时间	$O (n \log_{2} n)$	$O (n \log_{2} n)$	$O (n^{2})$
空间（全部来自递归栈）	$O (\log_{2} n)$	$O (\log_{2} n)$	$O (n)$

枢轴选取的三种优化

最坏情况的根源是枢轴选得太偏，所以优化都围绕枢轴：

随机选取：在 [low, high] 随机挑一个与 A[low] 交换再划分。任何固定输入都不会稳定触发最坏，期望 $O (n \log_{2} n)$ 。
三数取中：取 A[low]、A[mid]、A[high] 的中间值调到 A[low]。专治"输入基本有序"——实测 $n = 1000$ 正序输入，取首元素时递归深度 999，三数取中只有 9。
小子表转插入排序：子表长度小于阈值（如 10）时改调直接插入排序，小规模下常数因子更小、省递归开销。

不稳定的最小反例逐步推演

{3a, 3b, 2}，pivot = A[0] = 3a：

步	动作	结果
初始	`low=0, high=2`	`_ 3b 2`
1	`A[2]=2 < 3` 停；`A[0]=A[2]`	`2 3b _`
2	`2`、`3b` 都 $\leq 3$ 故 `low++` 两次，`low == high = 2` 退出	`2 3b _`
3	`A[2] = pivot = 3a`	`2 3b 3a`

3b 排到了 3a 前面。根源：枢轴 3a 从下标 0 一步搬到下标 2，跨过了与它相等的 3b，而两者从未被直接比较过——与希尔排序、简单选择排序、堆排序不稳定的根源完全相同。

考点速记

三条结论：

效率取决于划分是否均匀，与逆序对多少无关——所以它最怕有序输入，与其他 $O (n^{2})$ 算法完全相反。
空间 = 递归深度 = 递归树高，不是 $O (1)$ ；先处理长/短分区只影响栈深，不影响递归次数。
一趟划分让枢轴就位，但枢轴不一定是极值；一趟后两部分只是块间有序。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

判某序列不可能是第 2 趟结果：四个选项里三个合法。逐个找"左边全小、右边全大"的元素，数够 2 个才合法。做法是扫一遍前缀最大值、再扫一遍后缀最小值。
由一次划分结果反推枢轴：给划分后的序列，找那个唯一满足"左 $\leq$ 它 $\leq$ 右"的元素。
一趟划分后 $P$ 、 $Q$ 两部分的性质：正确的是"块间有序"。块内有序 ✗、个数大致相等 ✗、不存在相等元素 ✗。
递归次数与什么有关：与初始排列有关、与分区处理顺序无关。"先处理较长/较短分区可以减少递归次数"都是错的——那只影响栈深。
宜采用什么存储方式：顺序存储。散列、链式、索引都不行。
什么时候用直插而不用快排：大部分已有序、元素很少、要求空间 $O (1)$ 、要求稳定——四条全对（详见直接插入排序）。
稳定性判断：不稳定，与希尔、堆排同列。

易错：快排在有序输入上最慢，不是最快。 这是它与所有其他 $O (n^{2})$ 算法相反的地方。

易错：空间不是 $O (1)$ 。 递归栈平均 $O (\log_{2} n)$ 、最坏 $O (n)$ 。

易错："先处理短分区能减少递归次数"是错的。 总递归次数由划分结果唯一决定，处理顺序只改变栈深。

教材出处

快速排序由冒泡排序改进而得、"一次交换可能消除多个逆序"、一趟划分的具体步骤与算法描述（算法 8.5 的 Partition / QSort / QuickSort）、以 ${49, 38, 65, 97, 76, 13, 27, 49}$ 为例的一趟划分与全过程（图 8.4）：严蔚敏《数据结构（C 语言版）》（第 2 版），p243–p245
最好情况的递推式 $T (n) = C n + 2 T (n / 2)$ 及其逐层展开、最坏情况"在待排序序列已经排好序的情况下，其递归树成为单支树"与 $KCN = n (n - 1) / 2$ 、"三者取中"规则、平均情况 $O (n \log_{2} n)$ ：同书 p245–p246
空间复杂度："快速排序是递归的……最大递归调用次数与递归树的深度一致，所以最好情况下的空间复杂度为 $O (\log_{2} n)$ ，最坏情况下为 $O (n)$ "：同书 p246
算法特点："记录非顺次的移动导致排序方法是不稳定的"；"排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构"；"当 $n$ 较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种"：同书 p246
"在快速排序中，当划分子区间的长度小于某值时，可以转而调用直接插入排序算法"：同书 p268

真题练习

2024Q82分 2023Q112分 2022Q112分 2019Q102分 2014Q112分 2011Q102分 2010Q102分

快速排序

一趟划分：让一个元素直接到达最终位置

先动手看一眼

代码与三处不能改的地方

最怕的输入，正好是别人最喜欢的

空间是递归栈，不是 $O (1)$

判"某序列能不能是第 $k$ 趟结果"

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（7题）

快速排序 ​

一趟划分：让一个元素直接到达最终位置 ​

先动手看一眼 ​

代码与三处不能改的地方 ​

最怕的输入，正好是别人最喜欢的 ​

空间是递归栈，不是 O(1) ​

判"某序列能不能是第 k 趟结果" ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（7题）

快速排序

一趟划分：让一个元素直接到达最终位置

先动手看一眼

代码与三处不能改的地方

最怕的输入，正好是别人最喜欢的

空间是递归栈，不是 $O (1)$

判"某序列能不能是第 $k$ 趟结果"

考点速记

相关知识

真题练习