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

优先使用 std::nth_element，因其是工业级快速选择实现，平均 O(n)，内置 pivot 随机化、小数组优化及重复值鲁棒处理；手写易在边界、pivot 选择和语义映射（如第 K 大需转为索引 n−k）上出错。

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

为什么 `std::nth_element` 比手写快排划分更值得优先用

标准库的 std::nth_element 就是 C++ 对快速选择算法的工业级实现，平均 O(n)，最坏 O(n²) 但实际极难触发。它不排序整个数组，只保证第 k 个位置放对了数，左边 ≤ 它、右边 ≥ 它（默认升序），所以找“第 K 大”时要传入 begin + (n - k) 这个迭代器位置。

手写 partition 很容易在边界处理、pivot 选择、循环不变量上出错，尤其当数组含重复值或 k 越界时崩溃或返回错误结果。而 std::nth_element 已经处理了这些细节，还做了 pivot 随机化和小数组插入排序优化。

实操建议：

头文件必须包含
确保 k 在有效范围：1 ≤ k ≤ nums.size()，否则行为未定义
若需第 K 大，别直接用 nth_element(nums.begin(), nums.begin() + k - 1, nums.end()) —— 这是找第 K 小
如原数组不能修改，先拷贝一份，std::nth_element 会原地重排

手写快速选择时 pivot 怎么选才不容易退化

选第一个或最后一个元素作 pivot，在已排序或逆序数组上会直接退化成 O(n²)。实践中应避免硬编码 nums[l] 或 nums[r]。

推荐做法是三数取中（median-of-three）或随机化：

三数取中：取 nums[l]、nums[(l+r)/2]、nums[r] 的中位数，交换到末尾再做 partition
更简单可靠的是随机化：用 std::uniform_int_distribution 生成 [l, r] 内索引，swap 到 r 位置
不要用 rand() % (r - l + 1)，低比特周期短，分布不均
partition 后，递归只进一边：若 pivot 索引 == k，直接返回；若 > k，只递归左半；否则递归右半

`std::nth_element` 和手写版在重复元素多时表现一样吗

不一样。标准库实现通常采用 introselect（introspective selection）：结合快速选择 + 堆选择 + 中位数的中位数，对重复值有更好鲁棒性。而朴素手写 partition 若没处理好相等情况（比如把等于 pivot 的全堆左边或右边），可能导致某侧始终不缩小，死循环或超时。

例如数组全是相同数字，手写代码若 partition 返回的 pivot 位置每次都不等于 k，且左右区间大小没变化，就会无限递归。正确做法是在 partition 中把等于 pivot 的元素均匀分到两侧，或用三路划分（low / mid / high 三段）。

实操注意点：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

手写三路划分时，lt 指向小于区尾，gt 指向大于区头，i 扫描中间，遇到等于 pivot 就跳过，避免移动
std::nth_element 不保证相等元素的相对顺序，也不保证左右两段内部有序 —— 这正是它比 std::sort 快的原因
如果业务要求稳定（相同值的相对位置不变），快速选择本身不满足，得换方案

查第 K 大时，传错迭代器位置导致结果为 0 或越界访问

这是最常踩的坑：std::nth_element 第二个参数是“要定位到第几个位置”的迭代器，不是“要找第几个大”。默认按升序排，所以第 1 大是最大值，位于 end - 1；第 K 大对应升序下标 n - k。

错误写法：nth_element(v.begin(), v.begin() + k, v.end()) → 实际拿到的是第 (k+1) 小（索引从 0 开始）。

正确写法示例：

vector<int> nums = {3,2,1,5,6,4};
int k = 2; // 要第 2 大 → 应是 5
nth_element(nums.begin(), nums.begin() + nums.size() - k, nums.end());
cout <p>若 <code>k</code> 是 1-based 输入，别忘了检查 <code>nums.size() - k</code> 是否 <code>>= 0</code>，否则 <code>begin() + negative</code> 是未定义行为。</p>
<p>另外，空容器调用 <code>nth_element</code> 是未定义行为，务必提前判空。</p>
<p>快速选择真正的复杂点不在算法逻辑，而在边界控制、pivot 鲁棒性和语义对齐——尤其是“第 K 大”这个说法和底层升序索引之间的映射，一不留神就差一位或方向反了。</p></int>