C++如何使用快速选择算法（QuickSelect）获取第K大数-C++-PHP中文网

QuickSelect 通过分区只递归目标侧，平均 O(n) 比排序快；核心是随机 pivot 和正确 partition（Lomuto/三路），std::nth_element 可简化但需注意索引与比较器。

c++如何使用快速选择算法（quickselect）获取第k大数

QuickSelect 的核心逻辑和为什么它比排序快

QuickSelect 不需要完全排序，只保证第 k 个位置（从 0 开始）的元素是全局第 k+1 小的数；要拿第 K 大，就等价于找第 n-K 小（n 是数组长度）。它复用快排的分区（partition）思想，平均时间复杂度 O(n)，最坏 O(n²) —— 但用随机 pivot 基本能避开退化。

常见错误是直接套用快排写法却没提前终止：每次 partition 后，只递归处理包含目标索引的那一侧，另一侧直接丢弃。

手写 partition 函数要注意的三个细节

标准 partition 返回的是 pivot 最终落点的下标，但不同实现对相等元素的处理不一致。C++ STL 的 std::nth_element 用的是「三路分区」变体，而手写推荐用 Lomuto 方案（更直观），注意：

必须在进入循环前随机交换 left 和某个 [left, right] 内的下标，否则面对已排序数组会爆 O(n²)
swap(arr[i], arr[j]) 后，i 和 j 的更新顺序不能错：Lomuto 中先让 i 自增再 swap，否则越界或漏比较
返回值必须是 pivot 的最终位置，且该位置左侧所有元素 ≤ pivot，右侧 ≥ pivot（不严格要求有序，但分区必须正确）

调用 std::nth_element 更简单但有陷阱

如果只是取第 K 大且不介意原数组被部分重排，std::nth_element 是最稳妥选择。但它默认按升序找第 n-K 小，不是第 K 大：

std::vector<int> arr = {3, 2, 1, 5, 6, 4};
int n = arr.size();
std::nth_element(arr.begin(), arr.begin() + (n - K), arr.end()); // 找第 K 大 → 索引 n-K
int result = arr[n - K];
</int>

容易踩的坑：

C++14

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

下载

传入的迭代器位置必须在 [begin, end) 范围内，K=0 或 K>n 会 UB
它不保证其余元素有序，只保证第 n-K 位左边 ≤ 它、右边 ≥ 它
如果要用自定义比较（比如降序找第 K 大），得传 std::greater()，此时第 K 大就变成 arr.begin() + K - 1，别混用

完整手写 QuickSelect 示例（含边界防护）

下面是一个带防护的最小可用实现，支持 0 ：

int quickSelect(std::vector<int>& arr, int left, int right, int k) {
    if (left == right) return arr[left];
    int pivotIndex = left + rand() % (right - left + 1);
    std::swap(arr[pivotIndex], arr[right]);
    int mid = partition(arr, left, right);
    if (k == mid) return arr[k];
    else if (k int findKthLargest(std::vector<int>& nums, int K) {
int n = nums.size();
return quickSelect(nums, 0, n - 1, n - K); // 转成找第 n-K 小
}
</int></int>

关键点：