QuickSelect 通过分区只递归目标侧，平均 O(n) 比排序快；核心是随机 pivot 和正确 partition（Lomuto/三路），std::nth_element 可简化但需注意索引与比较器。
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 大：
立即学习“C++免费学习笔记（深入）”；
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];
容易踩的坑：
- 传入的迭代器位置必须在
[begin, end)范围内，K=0或K>n会 UB - 它不保证其余元素有序，只保证第
n-K位左边 ≤ 它、右边 ≥ 它 - 如果要用自定义比较（比如降序找第 K 大），得传
std::greater<int>()</int>，此时第 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 < mid) return quickSelect(arr, left, mid - 1, k);
else return quickSelect(arr, mid + 1, right, k);
}
<p>int findKthLargest(std::vector<int>& nums, int K) {
int n = nums.size();
return quickSelect(nums, 0, n - 1, n - K); // 转成找第 n-K 小
}
关键点：
-
partition函数里，right是 pivot 所在位置，循环结束时必须把 pivot 换到mid并返回mid - 递归调用前务必检查
left ，否则栈溢出 - 生产环境建议加
srand(time(nullptr))，但单元测试中应固定 seed 以便复现
最常被忽略的是：当数组含大量重复元素时，Lomuto 分区可能退化；此时改用 Hoare 分区或三路分区（类似快排的 three-way partition）才能稳定性能。
