如何用平均O(n)时间复杂度实现快速选择算法查找数组中第K大的数？

本文共计1004个文字，预计阅读时间需要5分钟。

许多初学者看到C++标准库中的`std::nth_element，就以为能直接用来找出第K大的数——结果发现：

真正要落地，得自己实现带随机 pivot 的 Lomuto 或 Hoare 分区，否则退化到 O(n²) 是常态。

• std::nth_element 默认按 std::less 排，即升序；找第 K 大需传 std::greater<int>()</int> 或转换下标：第 K 大 = 第 n-K 小（0-indexed）
• 它内部虽用快速选择思想，但不可控 pivot 策略，无法满足算法题对“过程可复现”“最坏情况说明”的要求
• 若原数组只读、或需返回索引而非值，标准库接口就不够用了

如何正确实现随机 pivot 的分区函数？

核心是避免每次选首/尾元素导致有序输入时 O(n²)。必须在 [left, right] 内随机选一个下标，再把它 swap 到末尾，再执行一次标准 partition —— 这步漏掉，随机性就白做了。

推荐用 Hoare 分区（双指针向中间收缩），比 Lomuto 更少交换、边界更稳：

立即学习“C++免费学习笔记（深入）”；

int partition(vector<int>& arr, int left, int right) { int idx = left + rand() % (right - left + 1); swap(arr[idx], arr[right]); int pivot = arr[right]; int i = left - 1, j = right + 1; while (true) { do i++; while (arr[i] < pivot); do j--; while (arr[j] > pivot); if (i >= j) return j; swap(arr[i], arr[j]); } }

• 注意：这里返回的是「最后一个小于等于 pivot 的位置」，所以递归时右半段从 j+1 开始
• 务必在每次调用前调用 srand(time(0))（仅首次），否则 rand() 总是同序列
• 若编译器支持 C++11，优先用 std::random_device + std::mt19937 替代 rand()

快速选择主逻辑怎么写才不越界、不漏 case？

关键不是写递归，而是想清楚当前区间 [left, right] 中 pivot 的最终位置 p 和目标位置 k 的关系。k 是 0-indexed 的目标下标（比如找第 3 大，数组长 n，则 k = n-3）。

递归分支只有三种可能，别写成四分支：

• 如果 p == k，直接返回 arr[p]
• 如果 p > k，说明第 k 小在左半段 → 递归处理 [left, p-1]
• 如果 p < k，说明在右半段 → 递归处理 [p+1, right]

常见错误是把 k 搞错成 1-indexed 后没调整区间，或者在 p < k 时错误地把 k 减去偏移量（其实不用减，因为整个数组下标不变，只是搜索范围缩小了）。

为什么平均 O(n) 但面试官总问最坏情况？

平均 O(n) 成立的前提是 pivot 均匀分布，而随机化后每次期望约一半元素被排除，级数收敛为线性。但最坏仍是 O(n²)，比如每次恰好选到最大值当 pivot —— 虽然概率极低，但理论上存在。

工程中可加保护：当递归深度超过 2*log2(n) 时，切到 std::sort 或堆（std::priority_queue）兜底；算法题一般不要求，但如果你写了「保证最坏 O(n)」的 median-of-medians，反而容易因常数过大被卡超时。

真正容易被忽略的是：多次调用时，全局 srand() 只能调一次；还有 vector 传参别用值传递，必须用引用，否则拷贝开销直接毁掉时间优势。