快速排序划分原理与退化陷阱
为什么在工程实践与算法竞赛中,快速排序(Quick Sort) 无需像归并排序那样额外开辟长度为 的辅助数组 tmp[],就能以极小的常数因子跑出 的飞快速度,稳坐“通用原地排序之王”的宝座;可一旦某个同学手写快排时图省事固定挑选区间首元素 a[l] 作为基准值(Pivot),面对一组明明已经从小到大排好序的测试数据 1、2、3、...、100000,程序不仅没变快,反而瞬间退化成 超时(TLE) 甚至把系统调用栈撑爆触发 RE(运行错误)?更进一步,如果题目只要求在 个无序整数中找出“第 小的数”,为什么借用快排的一次基准划分就能把复杂度直接压到惊人的 线性时间?在 GESP 五级认证以及 CSP-J/S 初赛与复赛中,快速排序的基准值(Pivot)双指针原地划分(Partition)机制、“先划分后递归”与归并“先递归后合并”的分治对比、非稳定性反例构造、极端数据退化为 的成因与防御策略,以及 快速选择(Quick Select)算法,是考察频率极高的核心重难点。本文将带你彻底吃透快速排序的底层脉络。
🎯 考纲锚点与核心痛点
📍 对应考点:深入掌握分治思想下的快速排序算法——双指针基准划分(Partition)原地交换过程、平均 与最坏 时间复杂度分析、递归调用栈空间开销、排序不稳定性本质,以及基于划分剪枝的 快速选择求第 小元素模型。 🎯 适用等级:
GESP 五级考点 | CSP-J/S 初赛/复赛必考
在初赛客观题、阅读程序推演与复赛手写分治代码时,考生最容易在以下三个痛点上失分:
- “双指针移动条件加错等号,遇全相等数据当场退化或死循环”:手写双指针划分时,搞不清内层循环
while (a[i] < pivot)为什么必须写严格小于<而不能写<=,一旦遇到全相等序列5、5、5、...、5,划分结果直接偏斜成 ,令复杂度雪崩至 ; - “混淆归并与快排的分治特性,误判空间复杂度为 ”:初赛判断题看到“快速排序是原地排序算法,因此额外空间复杂度为 ”便盲目打勾,忽略了递归调用栈在平均情况下占用 、最坏情况下占用 栈空间的关键事实;
- “百万级数据求第 小数仍无脑全量排序导致 TLE”:不理解快排划分天然具备的“定界剪枝”能力——每次划分后目标位置 只可能落在左半或右半其中一侧,单侧递归即可将 降维打击至线性期望时间 !
🧠 一、 核心原理深度拆解(有理论)
1. 同门分治双雄:归并排序 vs 快速排序
归并排序与快速排序同属**分治法(Divide and Conquer)**的巅峰之作,但两者的发力时机截然相反:
- 归并排序是“先递归、后干活(重在合并 Combine)”:切分阶段不看元素大小,无脑从下标正中间
mid = l + (r - l) / 2对半劈开();等左右两半各自递归排好序后,再耗费 时间与 额外数组tmp[]做双指针归并。 - 快速排序是“先干活、后递归(重在划分 Partition)”:在递归深入之前,先在当前区间
[l, r]中挑出一个基准值(Pivot),耗费 时间通过双指针相向扫描与原地交换,把不大于基准值的元素统统赶到左半阵营,把不小于基准值的元素统统赶到右半阵营;一旦左右阵营划清界限,左半任意元素本就小于等于右半任意元素,只需分别递归排好左半和右半,回溯时无需任何合并操作( 零开销),整个数组便已天然全局有序!
| 核心维度 | 二路归并排序(Merge Sort) | 快速排序(Quick Sort) |
|---|---|---|
| 分治发力点 | 先无脑对半切分,回溯时归并干活 | 先按基准值原地划分干活,再递归两侧 |
| 最好 / 平均时间 | 恒为 | (常数极小、缓存友好) |
| 最坏时间复杂度 | 恒为 (无惧毒瘤数据) | (每次基准恰好选到最大/最小值) |
| 额外空间复杂度 | (需辅助数组 tmp[] + 递归栈) | 平均 、最坏 (递归调用栈) |
| 排序稳定性 | 稳定(合并时 a[i] <= a[j] 左优先) | 不稳定(跨距离交换会打乱相等元素先后次序) |
2. 灵魂操作:Hoare 双指针原地划分与“不稳定性”微观图解
竞赛中最简洁、最不易写挂的快排模板采用 Hoare 双指针相向划分法:取区间中点元素 pivot = a[l + (r - l) / 2] 作为基准值,左指针 i 从 l 出发向右寻找第一个 >= pivot 的“违章大数”,右指针 j 从 r 出发向左寻找第一个 <= pivot 的“违章小数”;若此时 i <= j,则交换 a[i] 与 a[j] 并令 i++、j--,直至双指针交错(i > j)停止。
我们以序列 [7, 2, 8, 5, 1, 6, 3](l = 0, r = 6,中点基准 pivot = a[3] = 5)为例,定格整趟划分轨迹:
====================================================================================
【Hoare 双指针原地划分(Partition)微观定格图 | 基准值 pivot = a[3] = 5】
初始状态: 下标 [0] [1] [2] [3] [4] [5] [6]
数值 7 2 8 (5) 1 6 3
▲ ▲
i=0(7>=5 停) j=6(3<=5 停)
➔ 第 1 次交换 swap(a[0], a[6]),随后 i++, j--:
数值 3 2 8 (5) 1 6 7
▲ ▲
i=1(2<5 过) j=5(6>5 过)
i=2(8>=5 停) j=4(1<=5 停)
➔ 第 2 次交换 swap(a[2], a[4]),随后 i++, j--:
数值 3 2 1 (5) 8 6 7
▲▲
i=3, j=3 (均停在 5,满足 i<=j)
➔ 第 3 次自身交换 swap(a[3], a[3]),随后 i++, j-- 得 j=2, i=4(i > j 循环结束!)
最终划分解剖:
左半子区间 a[0..j] = [3, 2, 1](全 <= 5) | a[3]=5 已归位 | 右半子区间 a[i..6] = [8, 6, 7](全 >= 5)
====================================================================================- 为什么快速排序是“不稳定”的?(3 元素极简反例秒证):
假设待排数组为
[4₁, 4₂, 2](为了区分两个相等的4,记左侧为 、右侧为 ),取中点pivot = a[1] = 4₂。左指针在i = 0处遇到 停下,右指针在j = 2处遇到 停下,一记远距离跨区交换swap(a[0], a[2]),数组瞬间变成[2, 4₂, 4₁]!原本排在前面的 被一脚踢到了 的右边,相等元素的相对次序彻底颠倒,故快速排序必定是不稳定排序。
3. 致命退化:为什么选首元素作基准会让“有序数组”雪崩为 ?
快速排序快慢的命门,完全取决于每次选出的基准值 pivot 能否把区间均匀一分为二:
====================================================================================
【理想均衡划分:每次取中位数附近】 【极端偏斜退化:有序数组 [1,2,3,4,5] 选首元素作基准】
[规模 n] ── 扫描 n [1, 2, 3, 4, 5] (pivot=1) ── 扫描 5 次
/ \ / \
[n/2] [n/2] ─ 扫描 n [空] [2, 3, 4, 5] (pivot=2) ── 扫描 4 次
/ \ / \ / \
[n/4] [n/4] [n/4] [n/4] ─ 扫描 n [空] [3, 4, 5] (pivot=3) ── 扫描 3 次
/ \
★ 树高仅 log₂n 层,每层总工作量 O(n) [空] [4, 5] (pivot=4) ── 扫描 2 次
★ 总时间 = O(n log n),栈深 = O(log n)
★ 树高退化为 n 层斜链!总扫描 = n+(n-1)+...+1 = O(n²)
★ 递归栈深暴涨至 O(n) 层,大数据下必触发 TLE 或爆栈 RE!
====================================================================================- 退化数学账单:当输入数组本就是升序
[1, 2, ..., n](或降序)且代码死板选取首元素a[l](或尾元素a[r])作为pivot时,每一轮划分都只能把基准值自己孤零零地剥离出来,剩余 个元素原封不动落入同一侧。递推式恶化为: 当 时,比较次数高达 次,且产生 层未释放的函数栈帧! - 实战三大防御武器:
- 中点取基准:写
pivot = a[l + (r - l) / 2],可直接化解升序/降序有序数组的退化; - 随机化取基准(Randomized Quick Sort):写
pivot = a[l + rand() % (r - l + 1)],让任何精心构造的静态毒瘤数据都无法稳定卡进最坏分支,数学期望复杂度严格锁定 ; - 三数取中法(Median-of-Three):取首元素
a[l]、中点a[mid]、尾元素a[r]三者的中位数作为基准(C++ STLstd::sort底层的内省排序 Introsort 正是结合了三数取中快排、堆排序兜底与小区间插入排序!)。
- 中点取基准:写
4. 降维打击: 快速选择(Quick Select)求第 小数
如果题目给定 个无序整数,不需要完整排好整个数组,只要求输出从小到大排在下标 (,对应第 小)的那个数,用 std::sort 需要 ,而利用快排划分思想的**快速选择算法(Quick Select)**只需 !
原理极其直观:一趟 Hoare 划分结束后,区间 [l, r] 被切分为左半 [l..j]、可能的中间归位点(当 j + 1 < i 时为 a[j + 1])与右半 [i..r],且左半所有元素 中间元素 右半所有元素。我们只需拿目标下标 k 与分界指针 j、i 比对:
- 若
k <= j:第 小的数必定藏在左半区间,直接丢弃整个右半区间,只递归quick_select(l, j, k); - 若
k >= i:第 小的数必定藏在右半区间,直接丢弃整个左半区间,只递归quick_select(i, r, k); - 若
j < k && k < i:说明a[k]恰好夹在j与i正中间,它此时就已经稳坐最终排好序的位置,直接返回a[k]!
- 为什么单侧递归是线性 而不是 ?
在均衡划分期望下,每次问题规模减半且只递归 1 个子区间,总扫描次数构成收敛的等比级数求和:
这也是 C++ STL 中
nth_element(a, a + k, a + n)能够在 平均时间内秒求第 小数的底层核心原理!
💡 考场黄金法则(背诵直接套用):
- 【快排时空与退化铁律】:快速排序基于分治“先原地划分、后递归两侧”,平均时间复杂度 ,最坏时间复杂度 (如对有序序列固定选首/尾元素作基准);属于不稳定排序;因存在递归调用栈,额外空间复杂度平均为 、最坏为 (绝非 )!
- 【双指针防退化与快速选择铁律】:Hoare 双指针内层条件严守严格不等号
a[i] < pivot与a[j] > pivot(遇相等元素停下交换以均分重复值);若仅求第 小元素,每轮划分后只向包含下标 的单侧递归,期望时间复杂度由 直降至 !
🔍 二、 具象代码与数据推演(有举例)
示例:追踪序列 [7, 2, 8, 5, 1, 6, 3] 的快速排序完整划分轨迹
下面给出一段标准 C++11 演示程序,打印每一次 partition 结束后的区间边界、基准值、交错指针 j 与 i 以及实时数组状态:
#include <iostream>
#include <algorithm>
using namespace std;
int a[7] = {7, 2, 8, 5, 1, 6, 3};
void quick_sort(int l, int r) {
if (l >= r) {
return;
}
int pivot = a[l + (r - l) / 2];
int i = l, j = r;
while (i <= j) {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
cout << "Partition [" << l << ".." << r << "] (pivot=" << pivot
<< ") -> j=" << j << ", i=" << i << " | arr: ";
for (int k = 0; k < 7; k++) {
cout << a[k] << (k == 6 ? "\n" : " ");
}
if (l < j) {
quick_sort(l, j);
}
if (i < r) {
quick_sort(i, r);
}
}
int main() {
quick_sort(0, 6);
return 0;
}逐轮递归划分内存快照与指针追踪表
| 调用轮次 | 当前区间 [l..r] | 中点基准 pivot | 本轮触发 swap(a[i], a[j]) 明细 | 结束时 (j, i) | 后续递归分支 | 划分后全局数组快照 |
|---|---|---|---|---|---|---|
| 第 1 轮 | [0..6] | a[3] = 5 | ① i=0(7), j=6(3) 互换② i=2(8), j=4(1) 互换③ i=3(5), j=3(5) 自换 | (2, 4) | 左 [0..2]右 [4..6] | 3 2 1 5 8 6 7 |
| 第 2 轮 | [0..2] | a[1] = 2 | ① i=0(3), j=2(1) 互换② i=1(2), j=1(2) 自换 | (0, 2) | l=0 不递归r=2 不递归 | 1 2 3 5 8 6 7 |
| 第 3 轮 | [4..6] | a[5] = 6 | ① i=4(8), j=5(6) 互换 | (4, 5) | 左 4<4 停右 [5..6] | 1 2 3 5 6 8 7 |
| 第 4 轮 | [5..6] | a[5] = 8 | ① i=5(8), j=6(7) 互换 | (5, 6) | 左右均只剩单元素,全部结束 | 1 2 3 5 6 7 8 |
程序标准输出:
Partition [0..6] (pivot=5) -> j=2, i=4 | arr: 3 2 1 5 8 6 7
Partition [0..2] (pivot=2) -> j=0, i=2 | arr: 1 2 3 5 8 6 7
Partition [4..6] (pivot=6) -> j=4, i=5 | arr: 1 2 3 5 6 8 7
Partition [5..6] (pivot=8) -> j=5, i=6 | arr: 1 2 3 5 6 7 8注意观察第 1 轮与第 2 轮:当 i 和 j 同时停在基准值自身(如 i = 3, j = 3)时,i++、j-- 会让 j = 2、i = 4 直接跨过下标 3,这意味着 a[3] = 5 连下层递归都不需要进,当场永久锁定最终排名!
⚡ 三、 考场高频避坑指南(正误辨析)
在 GESP 五级客观题与 CSP-J 阅读程序、复赛手写分治中,以下三个深坑堪称高频“重灾区”:
❌ 易错点 1:把内层指针推进条件写成 <= pivot 和 >= pivot!
- 错误写法:
while (i <= j && a[i] <= pivot) i++; // 错误加了等号! while (i <= j && a[j] >= pivot) j--; // 错误加了等号! - 为什么错:一旦评测机喂入一组含大量重复值甚至全相等的数据(如 个
5:[5, 5, 5, ..., 5],这在竞赛测试点中极为常见!),左指针i会因为5 <= 5一路狂奔冲穿右边界,导致整趟划分极端偏斜成 与 ,直接从 退化成 TLE(若未加越界保护甚至直接数组越界 RE)! - 正确规范:内层推进必须严格写
while (a[i] < pivot) i++;与while (a[j] > pivot) j--;。这样遇到等于pivot的元素时双指针都会停下交换并各进一步,面对全相等数组时i和j会在正中间完美交汇,严格对半切分,稳保 !
❌ 易错点 2:掉进文字游戏——误判快排额外空间复杂度为 !
- 经典假命题:“归并排序需要 辅助数组,而快速排序直接在原数组上交换元素,不需要辅助数组,因此快速排序的空间复杂度为 。”
- 为什么错:在算法分析中,递归调用栈帧消耗的内存同样计入额外空间复杂度!快速排序虽然没有开辟 辅助数组,但每递归深入一层都要在系统栈上保存局部变量
l、r、i、j与返回地址:平均递归深度为 ,最坏退化深度为 。 - 正确规范:考场作答务必精确表述——快速排序的平均空间复杂度为 ,最坏空间复杂度为 ;在四大基础比较排序(冒泡、选择、插入、快排/归并)中,冒泡、简单选择、直接插入与堆排序才是真正的 额外空间!
❌ 易错点 3:在 while (i <= j) 划分期间直接取 a[mid] 当基准,而不是先存进变量 pivot!
- 错误写法:不定义值变量
int pivot = a[mid];,而是在循环里每次写while (a[i] < a[mid]) i++;。 - 为什么错:在双指针交换过程中,原本位于下标
mid处的元素极有可能在某次swap(a[i], a[j])时被换走到别的位置(例如上面第 3 轮中a[5]=6就被换到了下标4)!此时a[mid]的数值已经偷梁换柱变成了别的数,后续比较基准彻底错乱,排出来的结果必然乱序 WA! - 正确规范:进入
while (i <= j)循环前,必须先用局部变量int pivot = a[l + (r - l) / 2];把基准元素的数值拷贝固定下来,循环内一律与常量值pivot比较!
📝 四、 真题实战演练与精析(有例题:3 道)
【例题 1 · 单选题】(GESP 五级 / CSP-J 初赛阅读程序推演:含重复基准值的双指针划分)
题目:给定长度为 8 的整型数组 int a[8] = {6, 9, 2, 5, 8, 3, 5, 4};,对其区间 l = 0, r = 7 执行如下一次快速排序双指针划分代码片段:
int pivot = a[l + (r - l) / 2];
int i = l, j = r, swaps = 0;
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
swap(a[i], a[j]);
swaps++;
i++;
j--;
}
}当外层 while (i <= j) 循环结束时,变量 swaps 的值以及数组 a[0..7] 的元素序列分别是( )
- A.
swaps = 2,数组为{4, 3, 2, 5, 8, 9, 5, 6} - B.
swaps = 3,数组为{4, 5, 2, 3, 8, 5, 9, 6} - C.
swaps = 3,数组为{4, 3, 2, 5, 5, 8, 9, 6} - D.
swaps = 4,数组为{4, 5, 2, 3, 5, 8, 9, 6}
🔍 答案与逐项排除解析:
- 正确答案:B
- 解析过程:
首先计算中点下标
l + (r - l) / 2 = 0 + 7 / 2 = 3,故基准值pivot = a[3] = 5,初始i = 0, j = 7:- 第 1 轮外层循环:
a[0] = 6不满足< 5,i停在0;a[7] = 4不满足> 5,j停在7。因0 <= 7,执行第 1 次交换swap(a[0], a[7]),数组变为{4, 9, 2, 5, 8, 3, 5, 6},swaps = 1,随后i = 1, j = 6; - 第 2 轮外层循环(核心陷阱位!):
a[1] = 9不满足< 5,i停在1;右指针检查a[6] = 5,注意条件是严格大于a[j] > 5,5 > 5为假,故j直接停在下标6(若误当成>=跳过a[6]走到a[5]=3,就会误入 A 选项陷阱,排除 A)!因1 <= 6,执行第 2 次交换swap(a[1], a[6]),数组变为{4, 5, 2, 5, 8, 3, 9, 6},swaps = 2,随后i = 2, j = 5; - 第 3 轮外层循环:
a[2] = 2 < 5推进至i = 3,a[3] = 5不满足< 5停在i = 3;a[5] = 3不满足> 5停在j = 5。因3 <= 5,执行第 3 次交换swap(a[3], a[5]),数组变为{4, 5, 2, 3, 8, 5, 9, 6},swaps = 3,随后i = 4, j = 4; - 第 4 轮外层循环:
a[4] = 8不满足< 5停在i = 4;a[4] = 8 > 5令j左移至3,a[3] = 3不满足> 5停在j = 3。此时i = 4, j = 3,i <= j不成立,不发生第 4 次交换(排除 C、D),外层循环立即终止!最终swaps = 3,数组序列为{4, 5, 2, 3, 8, 5, 9, 6},锁定 B。(顺便可以看到:原下标6的第二个5跑到了下标1,而原下标3的第一个5跑到了下标5,直观印证了快排的不稳定性!)
- 第 1 轮外层循环:
【例题 2 · 判断题】(GESP 五级考纲概念辨析:最坏退化条件与空间代价)
题目:对一个已经按从小到大排好序的 元数组执行快速排序时,若每次划分均固定选取当前子区间的第一个元素作为基准值(Pivot),则算法不仅没有因“原本有序”而提速,反而会退化到最坏时间复杂度 ,且递归调用栈的空间开销也会达到 。( )
🔍 答案与反例证明:
- 结论:正确(√)
- 辨析证明:
- 许多初学者容易将快速排序与“加了提前终止标志的冒泡排序”或“直接插入排序”(这两者在数组已有序时为最好情况 )混淆;
- 在快速排序中,当数组严格递增有序(如
1、2、3、...、n)且每次固定取区间首元素a[l]为基准时,a[l]恰为整个子区间的最小值:每次耗费线性时间扫描整个区间后,左子区间长度为 、右子区间长度为 ,完全丧失对半折半效果; - 总比较次数累加为 ,同时递归树退化为深度为 的单链,系统调用栈帧层数达到 。故该命题完全正确。
【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛高频模板:快速选择求第 小的数)
题目描述:实验室采集了 个传感器响应延迟数据(),第 个数据为整数 (,可能包含相同数值)。现需要快速定位将这 个数据从小到大排序后,排在第 个位置(,即从 开始计数的第 小元素)的数值是多少。请运用分治划分与**快速选择(Quick Select)**思想编写 期望时间复杂度的程序求解。
输入格式: 第一行包含两个正整数 和 ,分别表示数据总个数与待查询的名次()。 第二行包含 个整数 ,以空格分隔。
输出格式: 输出一行一个整数,表示从小到大排在第 位的数值。
💡 算法建模与避坑要点:
- 下标映射对齐:题目给定的 是从 开始计数的名次,而数组
a[0..n-1]从 开始编号,因此传入quick_select(0, n - 1, k - 1)查找目标下标target = k - 1; - 单侧剪枝递归:每轮用 Hoare 双指针划分完毕后,数组裂变为
[l..j]、可能的独立归位点(当j + 1 < i时)以及[i..r]。若target <= j只递归左区间;若target >= i只递归右区间;否则说明j < target < i,此时a[target]已经精准归位,直接返回a[target],期望复杂度严格 !
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int a[MAXN];
int quick_select(int l, int r, int target) {
if (l >= r) {
return a[l];
}
int pivot = a[l + (r - l) / 2];
int i = l, j = r;
while (i <= j) {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
// 单侧递归剪枝:只进入包含目标下标 target 的那一侧
if (target <= j) {
return quick_select(l, j, target);
}
if (target >= i) {
return quick_select(i, r, target);
}
return a[target];
}
int main() {
int n, k;
cin >> n >> k;
for (int idx = 0; idx < n; idx++) {
cin >> a[idx];
}
cout << quick_select(0, n - 1, k - 1) << endl;
return 0;
}- 输入样例 1:
7 3 7 2 8 5 1 6 3 - 输出样例 1:(样例 1 解释:从小到大排序后序列为
31、2、3、5、6、7、8,排在第 3 位的元素下标为2,数值为3;首轮划分pivot = 5后j = 2, i = 4,因目标下标2 <= j直接丢弃右半[4..6],仅在左半[0..2]中继续定位。) - 输入样例 2:
6 4 5 1 5 2 5 3 - 输出样例 2:(样例 2 解释:含重复元素的序列从小到大排列为
51、2、3、5、5、5,第 4 小的元素为5。)
本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。
GESP/CSP认证交流QQ群: 688906745
