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

快速选择算法能定位第K大值的下标，是因为它通过维护下标数组并按对应值比较，确保partition过程不改变原数组而只重排索引；当算法收敛时，下标数组中对应位置即为原始索引。

c++实现快速选择算法查找第k大数值所在位置 _ 平均时间复杂度分析【源码】

快速选择算法为什么能定位第K大值的下标，而不是只返回值

快速选择算法本质是快排的剪枝版，它不保证整个数组有序，但能确保某次划分后，轴点（pivot）的最终位置恰好是目标序号。要返回“位置”而非“值”，关键是在每次 partition 后不丢弃原始索引信息——不能对原数组做无痕排序，而应操作索引数组或携带下标元组。

常见错误是直接对数值数组调用 std::nth_element 或手写快选，结果只能拿到第K大值，却不知道它原来在哪儿。正确做法是：维护一个下标数组 indices，按对应值排序该数组，即用 values[indices[i]] 比较大小。

初始化 indices 为 {0, 1, 2, ..., n-1}
在 partition 中比较逻辑改为 values[indices[i]] > values[indices[pivot]]
递归时只重排 indices 的子区间，values 始终不动
当分区收敛到单个下标时，indices[left] 就是原数组中第K大值的原始位置

std::nth_element 能不能直接用？要注意什么

可以，但必须配合自定义比较器和索引绑定，否则它只重排数值本身。标准库函数 std::nth_element 默认按值排序，若传入原始 vector，原数组会被修改，原始位置彻底丢失。

安全用法是传入下标容器，并用 lambda 指定比较规则：

vector<int> values = {3, 2, 1, 5, 6, 4};
vector<size_t> indices(values.size());
iota(indices.begin(), indices.end(), 0);
size_t k = 2; // 求第2大 → 实际是升序下标 n-k
nth_element(indices.begin(), indices.begin() + k - 1, indices.end(),
    [&](size_t i, size_t j) { return values[i] > values[j]; });
// 此时 indices[k-1] 就是原数组中第K大值的下标
</size_t></int>

注意：std::nth_element 是部分排序，平均复杂度 O(n)，但最坏 O(n²)；它不保证前K个元素有序，只保证第K位正确、左边≤右边≥（依比较器而定）。

C++14

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

下载

手写 partition 时最容易错的边界和循环条件

手写快选的 partition 函数，90% 的 bug 出在三处：轴点选择策略、双指针越界判断、递归区间闭合性。尤其当目标是“第K大”时，容易混淆升序/降序逻辑。

轴点别用 arr[left] 硬编码——用 arr[left + rand() % (right - left + 1)] 随机交换到右端，避免已排序输入退化
双指针 i 和 j 初始化为 left 和 right - 1（若轴点放 right），循环内先移动再比较，防止越界访问
比较条件必须与目标一致：求第K大 → arr[i] > pivot 才停，否则会把大数扫到右边去
递归调用时，若轴点最终位置是 p，则第K大对应升序下标 n - k，需判断 p == n-k、p > n-k、p 三种情况，区间传递用 [left, p-1] 和 [p+1, right]，别漏掉 =