快速排序划分原理与退化陷阱

快速排序划分原理与退化陷阱

为什么在工程实践与算法竞赛中,快速排序(Quick Sort) 无需像归并排序那样额外开辟长度为 nn 的辅助数组 tmp[],就能以极小的常数因子跑出 O(nlog⁡n)O(n \log n) 的飞快速度,稳坐“通用原地排序之王”的宝座;可一旦某个同学手写快排时图省事固定挑选区间首元素 a[l] 作为基准值(Pivot),面对一组明明已经从小到大排好序的测试数据 1、2、3、...、100000,程序不仅没变快,反而瞬间退化成 O(n2)O(n^2) 超时(TLE) 甚至把系统调用栈撑爆触发 RE(运行错误)?更进一步,如果题目只要求在 5×1065 \times 10^6 个无序整数中找出“第 kk 小的数”,为什么借用快排的一次基准划分就能把复杂度直接压到惊人的 O(n)O(n) 线性时间?在 GESP 五级认证以及 CSP-J/S 初赛与复赛中,快速排序的基准值(Pivot)双指针原地划分(Partition)机制、“先划分后递归”与归并“先递归后合并”的分治对比、非稳定性反例构造、极端数据退化为 O(n2)O(n^2) 的成因与防御策略,以及 O(n)O(n) 快速选择(Quick Select)算法,是考察频率极高的核心重难点。本文将带你彻底吃透快速排序的底层脉络。

🎯 考纲锚点与核心痛点

📍 对应考点:深入掌握分治思想下的快速排序算法——双指针基准划分(Partition)原地交换过程、平均 O(nlog⁡n)O(n \log n) 与最坏 O(n2)O(n^2) 时间复杂度分析、递归调用栈空间开销、排序不稳定性本质,以及基于划分剪枝的 O(n)O(n) 快速选择求第 kk 小元素模型。 🎯 适用等级:GESP 五级考点 | CSP-J/S 初赛/复赛必考

在初赛客观题、阅读程序推演与复赛手写分治代码时,考生最容易在以下三个痛点上失分:

  1. “双指针移动条件加错等号,遇全相等数据当场退化或死循环”:手写双指针划分时,搞不清内层循环 while (a[i] < pivot) 为什么必须写严格小于 < 而不能写 <=,一旦遇到全相等序列 5、5、5、...、5,划分结果直接偏斜成 1:(n−1)1 : (n - 1),令复杂度雪崩至 O(n2)O(n^2);
  2. “混淆归并与快排的分治特性,误判空间复杂度为 O(1)O(1)”:初赛判断题看到“快速排序是原地排序算法,因此额外空间复杂度为 O(1)O(1)”便盲目打勾,忽略了递归调用栈在平均情况下占用 O(log⁡n)O(\log n)、最坏情况下占用 O(n)O(n) 栈空间的关键事实;
  3. “百万级数据求第 kk 小数仍无脑全量排序导致 TLE”:不理解快排划分天然具备的“定界剪枝”能力——每次划分后目标位置 kk 只可能落在左半或右半其中一侧,单侧递归即可将 O(nlog⁡n)O(n \log n) 降维打击至线性期望时间 O(n)O(n)!

🧠 一、 核心原理深度拆解(有理论)

1. 同门分治双雄:归并排序 vs 快速排序

归并排序与快速排序同属**分治法(Divide and Conquer)**的巅峰之作,但两者的发力时机截然相反:

  • 归并排序是“先递归、后干活(重在合并 Combine)”:切分阶段不看元素大小,无脑从下标正中间 mid = l + (r - l) / 2 对半劈开(O(1)O(1));等左右两半各自递归排好序后,再耗费 O(n)O(n) 时间与 O(n)O(n) 额外数组 tmp[] 做双指针归并。
  • 快速排序是“先干活、后递归(重在划分 Partition)”:在递归深入之前,先在当前区间 [l, r] 中挑出一个基准值(Pivot),耗费 O(n)O(n) 时间通过双指针相向扫描与原地交换,把不大于基准值的元素统统赶到左半阵营,把不小于基准值的元素统统赶到右半阵营;一旦左右阵营划清界限,左半任意元素本就小于等于右半任意元素,只需分别递归排好左半和右半,回溯时无需任何合并操作(O(1)O(1) 零开销),整个数组便已天然全局有序!
核心维度二路归并排序(Merge Sort)快速排序(Quick Sort)
分治发力点先无脑对半切分,回溯时归并干活先按基准值原地划分干活,再递归两侧
最好 / 平均时间恒为 O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)(常数极小、缓存友好)
最坏时间复杂度恒为 O(nlog⁡n)O(n \log n)(无惧毒瘤数据)O(n2)O(n^2)(每次基准恰好选到最大/最小值)
额外空间复杂度O(n)O(n)(需辅助数组 tmp[] + 递归栈)平均 O(log⁡n)O(\log n)、最坏 O(n)O(n)(递归调用栈)
排序稳定性稳定(合并时 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,记左侧为 414_1、右侧为 424_2),取中点 pivot = a[1] = 4₂。左指针在 i = 0 处遇到 41≥424_1 \ge 4_2 停下,右指针在 j = 2 处遇到 2≤422 \le 4_2 停下,一记远距离跨区交换 swap(a[0], a[2]),数组瞬间变成 [2, 4₂, 4₁]!原本排在前面的 414_1 被一脚踢到了 424_2 的右边,相等元素的相对次序彻底颠倒,故快速排序必定是不稳定排序。

3. 致命退化:为什么选首元素作基准会让“有序数组”雪崩为 O(n2)O(n^2)?

快速排序快慢的命门,完全取决于每次选出的基准值 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 时,每一轮划分都只能把基准值自己孤零零地剥离出来,剩余 n−1n - 1 个元素原封不动落入同一侧。递推式恶化为: T(n)=T(n−1)+O(n)=(n−1)+(n−2)+⋯+1=n(n−1)2=O(n2)T(n) = T(n - 1) + O(n) = (n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = O(n^2) 当 n=105n = 10^5 时,比较次数高达 ≈5×109\approx 5 \times 10^9 次,且产生 10510^5 层未释放的函数栈帧!
  • 实战三大防御武器:
    1. 中点取基准:写 pivot = a[l + (r - l) / 2],可直接化解升序/降序有序数组的退化;
    2. 随机化取基准(Randomized Quick Sort):写 pivot = a[l + rand() % (r - l + 1)],让任何精心构造的静态毒瘤数据都无法稳定卡进最坏分支,数学期望复杂度严格锁定 O(nlog⁡n)O(n \log n);
    3. 三数取中法(Median-of-Three):取首元素 a[l]、中点 a[mid]、尾元素 a[r] 三者的中位数作为基准(C++ STL std::sort 底层的内省排序 Introsort 正是结合了三数取中快排、堆排序兜底与小区间插入排序!)。

4. 降维打击:O(n)O(n) 快速选择(Quick Select)求第 kk 小数

如果题目给定 nn 个无序整数,不需要完整排好整个数组,只要求输出从小到大排在下标 kk(0≤k<n0 \le k < n,对应第 k+1k + 1 小)的那个数,用 std::sort 需要 O(nlog⁡n)O(n \log n),而利用快排划分思想的**快速选择算法(Quick Select)**只需 O(n)O(n)!

原理极其直观:一趟 Hoare 划分结束后,区间 [l, r] 被切分为左半 [l..j]、可能的中间归位点(当 j + 1 < i 时为 a[j + 1])与右半 [i..r],且左半所有元素 ≤\le 中间元素 ≤\le 右半所有元素。我们只需拿目标下标 k 与分界指针 j、i 比对:

  1. 若 k <= j:第 kk 小的数必定藏在左半区间,直接丢弃整个右半区间,只递归 quick_select(l, j, k);
  2. 若 k >= i:第 kk 小的数必定藏在右半区间,直接丢弃整个左半区间,只递归 quick_select(i, r, k);
  3. 若 j < k && k < i:说明 a[k] 恰好夹在 j 与 i 正中间,它此时就已经稳坐最终排好序的位置,直接返回 a[k]!
  • 为什么单侧递归是线性 O(n)O(n) 而不是 O(nlog⁡n)O(n \log n)? 在均衡划分期望下,每次问题规模减半且只递归 1 个子区间,总扫描次数构成收敛的等比级数求和: T(n)=n+n2+n4+n8+⋯<n∑t=0∞12t=2n=O(n)T(n) = n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots < n \sum_{t = 0}^{\infty} \frac{1}{2^t} = 2n = O(n) 这也是 C++ STL 中 nth_element(a, a + k, a + n) 能够在 O(n)O(n) 平均时间内秒求第 kk 小数的底层核心原理!

💡 考场黄金法则(背诵直接套用):

  1. 【快排时空与退化铁律】:快速排序基于分治“先原地划分、后递归两侧”,平均时间复杂度 O(nlog⁡n)O(n \log n),最坏时间复杂度 O(n2)O(n^2)(如对有序序列固定选首/尾元素作基准);属于不稳定排序;因存在递归调用栈,额外空间复杂度平均为 O(log⁡n)O(\log n)、最坏为 O(n)O(n)(绝非 O(1)O(1))!
  2. 【双指针防退化与快速选择铁律】:Hoare 双指针内层条件严守严格不等号 a[i] < pivot 与 a[j] > pivot(遇相等元素停下交换以均分重复值);若仅求第 kk 小元素,每轮划分后只向包含下标 kk 的单侧递归,期望时间复杂度由 O(nlog⁡n)O(n \log n) 直降至 O(n)O(n)!

🔍 二、 具象代码与数据推演(有举例)

示例:追踪序列 [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--; // 错误加了等号!
    
  • 为什么错:一旦评测机喂入一组含大量重复值甚至全相等的数据(如 10510^5 个 5:[5, 5, 5, ..., 5],这在竞赛测试点中极为常见!),左指针 i 会因为 5 <= 5 一路狂奔冲穿右边界,导致整趟划分极端偏斜成 (n−1)(n - 1) 与 11,直接从 O(nlog⁡n)O(n \log n) 退化成 O(n2)O(n^2) TLE(若未加越界保护甚至直接数组越界 RE)!
  • 正确规范:内层推进必须严格写 while (a[i] < pivot) i++; 与 while (a[j] > pivot) j--;。这样遇到等于 pivot 的元素时双指针都会停下交换并各进一步,面对全相等数组时 i 和 j 会在正中间完美交汇,严格对半切分,稳保 O(nlog⁡n)O(n \log n)!

❌ 易错点 2:掉进文字游戏——误判快排额外空间复杂度为 O(1)O(1)!

  • 经典假命题:“归并排序需要 O(n)O(n) 辅助数组,而快速排序直接在原数组上交换元素,不需要辅助数组,因此快速排序的空间复杂度为 O(1)O(1)。”
  • 为什么错:在算法分析中,递归调用栈帧消耗的内存同样计入额外空间复杂度!快速排序虽然没有开辟 O(n)O(n) 辅助数组,但每递归深入一层都要在系统栈上保存局部变量 l、r、i、j 与返回地址:平均递归深度为 O(log⁡n)O(\log n),最坏退化深度为 O(n)O(n)。
  • 正确规范:考场作答务必精确表述——快速排序的平均空间复杂度为 O(log⁡n)O(\log n),最坏空间复杂度为 O(n)O(n);在四大基础比较排序(冒泡、选择、插入、快排/归并)中,冒泡、简单选择、直接插入与堆排序才是真正的 O(1)O(1) 额外空间!

❌ 易错点 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. 第 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. 第 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. 第 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. 第 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,直观印证了快排的不稳定性!)

【例题 2 · 判断题】(GESP 五级考纲概念辨析:最坏退化条件与空间代价)

题目:对一个已经按从小到大排好序的 nn 元数组执行快速排序时,若每次划分均固定选取当前子区间的第一个元素作为基准值(Pivot),则算法不仅没有因“原本有序”而提速,反而会退化到最坏时间复杂度 O(n2)O(n^2),且递归调用栈的空间开销也会达到 O(n)O(n)。( )

🔍 答案与反例证明:

  • 结论:正确(√)
  • 辨析证明:
    1. 许多初学者容易将快速排序与“加了提前终止标志的冒泡排序”或“直接插入排序”(这两者在数组已有序时为最好情况 O(n)O(n))混淆;
    2. 在快速排序中,当数组严格递增有序(如 1、2、3、...、n)且每次固定取区间首元素 a[l] 为基准时,a[l] 恰为整个子区间的最小值:每次耗费线性时间扫描整个区间后,左子区间长度为 00、右子区间长度为 n−1n - 1,完全丧失对半折半效果;
    3. 总比较次数累加为 (n−1)+(n−2)+⋯+1=n(n−1)2=O(n2)(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = O(n^2),同时递归树退化为深度为 nn 的单链,系统调用栈帧层数达到 O(n)O(n)。故该命题完全正确。

【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛高频模板:快速选择求第 kk 小的数)

题目描述:实验室采集了 nn 个传感器响应延迟数据(1≤n≤1051 \le n \le 10^5),第 ii 个数据为整数 aia_i(−109≤ai≤109-10^9 \le a_i \le 10^9,可能包含相同数值)。现需要快速定位将这 nn 个数据从小到大排序后,排在第 kk 个位置(1≤k≤n1 \le k \le n,即从 11 开始计数的第 kk 小元素)的数值是多少。请运用分治划分与**快速选择(Quick Select)**思想编写 O(n)O(n) 期望时间复杂度的程序求解。

输入格式: 第一行包含两个正整数 nn 和 kk,分别表示数据总个数与待查询的名次(1≤k≤n1 \le k \le n)。 第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n,以空格分隔。

输出格式: 输出一行一个整数,表示从小到大排在第 kk 位的数值。

💡 算法建模与避坑要点:

  1. 下标映射对齐:题目给定的 kk 是从 11 开始计数的名次,而数组 a[0..n-1] 从 00 开始编号,因此传入 quick_select(0, n - 1, k - 1) 查找目标下标 target = k - 1;
  2. 单侧剪枝递归:每轮用 Hoare 双指针划分完毕后,数组裂变为 [l..j]、可能的独立归位点(当 j + 1 < i 时)以及 [i..r]。若 target <= j 只递归左区间;若 target >= i 只递归右区间;否则说明 j < target < i,此时 a[target] 已经精准归位,直接返回 a[target],期望复杂度严格 O(n)O(n)!
#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:
    3
    (样例 1 解释:从小到大排序后序列为 1、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:
    5
    (样例 2 解释:含重复元素的序列从小到大排列为 1、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

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于