C++实现快速选择算法查找第K大数 _ O(n)平均时间复杂度实现【源码】-C++-PHP中文网

std::nth_element是首选，因其为工业级快速选择实现，平均o(n)、最坏o(n²)，经三数取中和插入排序等优化；手写易在pivot选择、分区细节和递归转换出错，且难防恶意输入导致性能退化。

c++实现快速选择算法查找第k大数 _ o(n)平均时间复杂度实现【源码】

标准库的 std::nth_element 就是快速选择算法的工业级实现，平均 O(n)、最坏 O(n²)，且经过大量优化（比如三数取中、小数组切分用插入排序）。自己重写容易在边界、pivot 选择、递归/迭代转换上出错，还可能更慢。

除非你在面试中被明确要求手写，或需定制 pivot 策略（如强制随机化防恶意输入），否则直接用它更稳妥。

头文件只需 #include <algorithm></algorithm>
调用形式：std::nth_element(begin, begin + k, end) —— 注意：它把第 k 小元素放到位置 begin + k，不是第 k 大
若要找第 K 大，等价于找第 n - K 小（0-indexed），即传入迭代器位置 v.begin() + n - K

最常见错误是固定取首/尾元素作 pivot，遇到已排序或逆序数组就会触发最坏情况。哪怕数据看似随机，攻击者也可能构造输入让性能崩塌。

必须引入随机性或更鲁棒策略：

推荐：std::random_device + std::uniform_int_distribution 随机选下标，swap 到末尾再 partition
次选：三数取中（取首、中、尾三值的中位数），但对特定模式仍可能失效
避免：每次无脑取 left 或 right —— 这在 LeetCode 测试用例里大概率超时

示例关键片段：

int rand_idx = left + dist(gen) % (right - left + 1);
std::swap(arr[rand_idx], arr[right]); // 把随机 pivot 换到最后

经典 Lomuto 分区法（单指针扫描）写错一个条件就崩：比如用 而不是 <code>，会导致 pivot 自身被重复交换；或者循环结束没把 pivot 放回正确位置。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

更稳的是 Hoare 分区（双指针向中间靠拢），但要注意：

别依赖“分区后 pivot 在最终位置”这个直觉来写递归终止条件，应严格比较 pos 与目标索引 k 的大小关系。

递归写法简洁，但深递归可能爆栈（尤其 worst-case 时递归深度达 n）。改成迭代需手动维护待处理区间，常见错误是：

真正省栈空间的关键，是每次只压入一个子区间（类似尾递归优化）：先处理较小一半，再用循环处理较大一半。但这会增加代码复杂度，日常建议直接用递归 + 随机 pivot，99% 场景够用。

边界和 pivot 随机化这两点，比算法名字里的“快速”更重要——没处理好，O(n) 就只是个幻觉。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！

C++实现快速选择算法查找第K大数 _ O(n)平均时间复杂度实现【源码】