快速选择（Quickselect）是什么？如何平均 O(n) 找第 K 大元素？

简化版

快速选择借用快排的分区（partition）：分区后基准（pivot）落到它最终该在的下标 p，若 p 正好是要找的下标就返回；否则只递归基准的一侧——目标在左就往左找、在右就往右找，另一半彻底丢掉。因为每次只处理一半，平均代价 n+n/2+n/4+… ≈ 2n，所以平均 O(n)（快排要两边都递归，是 O(n log n)）；最坏 O(n²)，用随机化基准避免。适合「找第 K 大 / Top K」而不需要全排序的场景。

详细版

「第 K 大」= 升序排列后下标为 n−k 的元素（第 K 小 = 下标 k−1）。

int findKthLargest(int[] a, int k) {
    int target = a.length - k;       // 第 k 大 → 升序第 (n-k) 个下标
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int p = partition(a, lo, hi);// 基准归位，返回其最终下标
        if (p == target) return a[p];
        else if (p < target) lo = p + 1;  // 目标在右侧，只找右边
        else hi = p - 1;                   // 目标在左侧，只找左边
    }
    return -1;
}
// 随机化 + Lomuto 分区，避免最坏退化
int partition(int[] a, int lo, int hi) {
    int r = lo + (int)(Math.random() * (hi - lo + 1));
    swap(a, r, hi);                  // 随机选基准，换到末尾
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a, i++, j);
    swap(a, i, hi);                  // 基准归位到 i
    return i;
}

和快排的唯一区别：快排分完区两边都递归；快速选择判断目标在哪半，只递归一半。
复杂度：平均 O(n)，最坏 O(n²)（基准每次都选到极值），空间 O(1)（迭代版）。
一定要随机化基准（或三数取中），否则对有序数组会稳定退化到 O(n²)。

完整版教学

一、问题：找第 K 大，不必全排序

「找第 K 大 / 第 K 小 / Top K」是超高频题。最直接的想法是排序后取第 K 个，O(n log n)。但其实我们并不关心其他元素的完整顺序——只想知道第 K 位上是谁。快速选择利用这一点，把平均复杂度降到 O(n)，比排序更优。

二、借用快排的分区：基准归位是关键

快速选择的地基是快排的 partition：选一个基准，一趟扫描把数组重排成「左边都比基准小 | 基准 | 右边都比基准大」，此时基准就到了它在完全有序数组里的最终位置 p。

这个 p 是决定性的信息：

若 p == target（要找的下标），那 a[p] 就是答案，直接返回；
若 p < target，目标比基准大，在右半，只需去右半 [p+1, hi] 继续找；
若 p > target，目标在左半，只去左半 [lo, p−1] 找。

每次分区都能确定一个元素的最终位置，并把搜索范围砍掉一半。

三、只递归一侧：为什么平均 O(n)

这是快速选择和快排的本质差别，也是它 O(n) 的来源：

快排：分区后左右两半都要递归排序 → T(n)=2T(n/2)+O(n)=O(n log n)。
快速选择：分区后只有一半含目标，只递归那一半 → T(n)=T(n/2)+O(n)。

期望情况下每次砍掉一半，总代价是 n + n/2 + n/4 + … ≈ 2n，也就是 O(n)。直观理解：全排序是「把每个元素都放到正确位置」，而我们只需要「把第 K 位放对」，省掉了另一半的工作。

四、代码细节：下标换算与分区

下标换算：升序数组里，第 K 大 = 下标 n−k；第 K 小 = 下标 k−1。想清楚要找的 target 是哪个，别把大小、下标算反。
分区实现：可用 Lomuto（以末元素为基准，好写）或 Hoare（双指针夹逼，交换更少）。上面用 Lomuto。
迭代 vs 递归：因为只递归一侧，可以直接写成 while 循环调整 lo/hi，空间 O(1)，也避免递归栈。

五、最坏 O(n²) 与随机化；和堆、BFPRT 对比

最坏情况：每次分区基准都恰好是极值（比如固定取末元素去处理有序数组），一次只能排除 1 个元素，退化成 n+(n−1)+…=O(n²)。
随机化基准：每次随机挑基准（如上面代码），任何特定输入都无法稳定触发最坏，期望 O(n)。这是实践标配。
BFPRT（中位数的中位数 / median of medians）：一种精心选基准的策略，能保证最坏也是 O(n)，但常数大、少用于工程。
对比堆解法：用大小为 K 的堆求 Top K 是 O(n log k)，空间 O(k)，且适合数据流/海量数据（不用把全部数据装进内存）；快速选择要求数据在内存里、会打乱原数组，但平均更快。面试常问二者取舍：数据能全放内存、允许改动、只求一次 → 快速选择；数据是流式或超大、需要稳定 O(n log k) → 堆。

六、递归式、合并证明与数字推演

这道题的分治闭环是：分区后枢轴处于排序后的最终下标，只需继续包含目标下标的一侧。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

平均 T(n)=T(n/2)+Θ(n)=Θ(n)，最坏 T(n)=T(n-1)+Θ(n)=Θ(n²)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：长度 9 找第 3 大等价找升序下标 6；若分区枢轴落在 4，只处理右侧而非两边。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：随机枢轴降低对抗输入风险；重复值多宜三路分区；第 K 大与 0-based 下标换算要明确。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

期望线性并不等于每轮恰好对半。随机枢轴有稳定概率落在中间区间，使剩余规模按几何速度缩小；把各轮分区成本相加可界为 n + 3n/4 + (3/4)^2n + ... = O(n)。工程实现仍应随机化或打乱输入，不能把固定末尾枢轴暴露给已排序或对抗数据。

八、常见误区与追问

误区：快速选择一定是 O(n)。 O(n) 是期望复杂度，糟糕枢轴可退化 O(n²)。
误区：分区后还要递归两侧。 只处理目标下标所在一侧。
误区：第 K 大的目标下标就是 K。 升序 0-based 通常是 n-K。
追问：为什么平均是线性？ 期望每轮只保留常数比例，n+n/2+n/4 收敛到 2n。
追问：要最坏线性怎么办？ 使用 BFPRT 中位数的中位数选枢轴，常数更大。
追问：与大小为 K 的堆相比？ 堆为 O(n log K)、O(K) 空间，适合流式；Quickselect 会改数组。

九、加强记忆

快速选择 = 快排的分区 + 只递归一侧。分区后基准落到最终下标 p：p==target 直接返回，否则只往含目标的那半找。因为每次砍一半、只处理一侧，n+n/2+…≈2n → 平均 O(n)，空间 O(1)。第 K 大对应升序下标 n−k。必须随机化基准防最坏 O(n²)。对比：堆求 Top K 是 O(n log k) 且适合数据流，快速选择平均更快但要改数组、需数据在内存。

简化版

详细版