std::nth_element是首选，因其是经优化的工业级快速选择实现，平均O(n)时间、原地执行且鲁棒；手写易在pivot选择、分区或剪枝上出错，导致最坏O(n²)退化。
为什么 std::nth_element 是首选，而不是手写快选
标准库的 std::nth_element 就是快速选择算法的工业级实现，平均时间复杂度 O(n)，原地完成、无需额外空间，且经过大量边界测试和优化。自己重写容易在分区逻辑、pivot 选择、递归/迭代转换上出错，尤其当输入含大量重复值或已排序时，性能可能退化到 O(n²)。
使用它最稳妥：
#include <algorithm>
#include <vector>
<p>int findKthLargest(std::vector<int>& nums, int k) {
// 找第 k 大 → 等价于找升序排列后下标为 nums.size() - k 的元素
std::nth_element(nums.begin(), nums.begin() + nums.size() - k, nums.end());
return nums[nums.size() - k];
}注意：该函数会修改原数组顺序；若不允许修改，需传入副本或用 std::partial_sort（但代价更高）。
手写快选时 pivot 选错会导致严重退化
常见错误是固定取 left 或 right 为 pivot —— 遇到已排序数组，每次只排除一个元素，复杂度飙升至 O(n²)。必须引入随机化或三数取中。
立即学习“C++免费学习笔记（深入）”；
推荐做法：
- 用
std::random_device和std::mt19937随机交换left和某随机位置，再取nums[left]为 pivot - 或对
nums[left]、nums[mid]、nums[right]排序后取中位数（避免额外分配） - 绝对不要用
rand() % (right - left + 1)—— 低比特随机性差，且未 seed 时默认为 1
分区后必须判断区间，不能无脑递归左右
快选的核心是“剪枝”：只递归包含目标索引的那一侧。若忽略这点，写成类似快排的双递归，就退化为 O(n log n) 甚至更差。
关键逻辑分支：
- 设分区后 pivot 最终落于位置
pos - 若
pos == k，直接返回nums[pos] - 若
pos > k，只需在[left, pos-1]中继续找 - 若
pos ，则去 <code>[pos+1, right]中找，注意此时目标索引变为k（不是k-pos-1），因为整个数组索引是全局的
错误写法示例：quickSelect(nums, pos+1, right, k-pos-1) —— 这是针对“找第 k 小且从 0 开始计数”的混淆，极易出错。
第 K 大和第 K 小的索引映射别硬背，现场推
面对“第 K 大”，别依赖记忆公式。每次按定义推一遍：
- 升序数组：
index = 0是最小，index = size-1是最大 - 所以第 1 大 →
index = size-1，第 2 大 →index = size-2，第 K 大 →index = size-K - 前提是 K 从 1 开始计数（LeetCode 等平台惯例），若 K 从 0 开始，则是
size-1-K
这个偏移一旦搞反，结果必然错，且很难通过小样例发现（比如 [3,2,1] 中找第 2 大，错写成 index=1 得到 2，看似对，但换 [1,2,3,4] 就暴露了）。
真正麻烦的是重复值场景——“第 K 大”语义本身不保证唯一性，std::nth_element 只保证位置正确，左侧 ≤、右侧 ≥，但不保证严格大于。如需严格第 K 个不同值，得先去重，那就不属于快选范畴了。
