C++ 实现快速选择算法查找第 K 大数值所在位置逻辑及其平均复杂度逻辑解析【源码】-C++-PHP中文网

std::nth_element不返回下标因只保证第k位有序，不保留原索引；需用索引数组+自定义比较函数做分区，避免重复值查找错误，时间复杂度期望O(n)。

c++ 实现快速选择算法查找第 k 大数值所在位置逻辑及其平均复杂度逻辑解析【源码】

为什么 `std::nth_element` 不返回下标而要自己实现分区逻辑

因为 std::nth_element 只保证第 k 个位置放好目标值，不保证该值在原数组中的原始索引被保留；若需「第 K 大数值的原始位置」（比如输入是带索引的结构体数组），必须手动维护索引映射，不能直接对值数组调用标准库。

常见错误是先复制值、排序/选第 K 大，再用 std::find 回原数组找——这在有重复值时会出错（可能找到错误的同值元素）。

正确做法：把原数组下标打包进数据结构，只对索引数组做 partition 操作
分区比较逻辑必须基于原数组值，但交换的是索引变量
避免拷贝原数组值，尤其当 T 是大对象时

手写快速选择时如何维护原始位置信息

核心是「不移动原数据，只重排索引」。假设输入为 std::vector nums，要找第 K 大（即升序下第 nums.size() - k 小），可定义索引数组：

std::vector<size_t> indices(nums.size());
std::iota(indices.begin(), indices.end(), 0);
</size_t>

然后对 indices 做快速选择，比较函数写成：

indices[k]

K 从 1 开始计数，务必校验 k > 0 && k
使用 size_t 避免有符号/无符号混用警告
递归实现易爆栈，生产环境建议用迭代版或 std::nth_element + 索引映射混合方案

平均时间复杂度 O(n) 的关键不是“每次砍半”，而是期望意义下的划分质量

快速选择的 O(n) 是期望复杂度，前提是每次 pivot 能把数组大致分成两段。最坏情况（每次选到最小/最大值作 pivot）仍是 O(n²)，比如已排序数组且用首/尾元素当 pivot。

C++14

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

下载

用随机 pivot 或三数取中（nums[l], nums[r], nums[(l+r)/2]）能极大降低退化概率
实际工程中，std::nth_element 通常采用 introselect：超深递归时自动切换到堆选择（O(n log k)）保底
不要误以为「平均 O(n)」意味着稳定快于排序；小数组（n std::sort 更快，因常数项低

一个安全、可调试的手写迭代版快速选择（返回原始下标）

以下代码片段跳过模板泛化，聚焦逻辑主干，适用于 std::vector：

size_t quickSelectIndex(const std::vector<int>& nums, size_t k) {
    size_t n = nums.size();
    if (k >= n) throw std::out_of_range("k out of bounds");
<pre class="brush:php;toolbar:false;">std::vector<size_t> indices(n);
std::iota(indices.begin(), indices.end(), 0);

size_t left = 0, right = n - 1;
while (left <p>}
</p></size_t>

注意：k 这里指升序第 k 小（0-indexed），要找第 K 大请传入 n - K（K 从 1 开始）。

真正容易被忽略的是：随机数种子没初始化会导致每次运行 pivot 相同，测试时看似正常，压测时突然卡死——记得在 main 开头加 srand(time(nullptr))，或改用 std::random_device。