std::nth_element是查找第k大/小元素的最优解：平均O(n)时间、原地操作、仅保证目标位置正确；需注意索引转换、越界检查、重复值不确定性及小数据时暴力法更优。
直接用 std::nth_element，别手写快排分区
绝大多数场景下，std::nth_element 是最优解：它平均时间复杂度 O(n)，原地操作，不改变整个数组有序性，只保证第 k 个位置放对元素。比完整排序（O(n log n)）快，比自己实现 partition 容易出错。
注意：std::nth_element 默认按升序找第 k 个（即第 k 小），要找第 K 大，得把索引转成 nums.begin() + (n - k)：
std::vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
int n = nums.size();
std::nth_element(nums.begin(), nums.begin() + (n - k), nums.end());
// 此时 nums[n-k] 就是第 k 大的值
- 索引别越界：确保
k在[1, n]范围内，否则n - k会是负数或超限 - 它不保证前/后部分有序，只保证“左边 ≤ 中间 ≤ 右边”，所以不能依赖
nums[n-k-1]一定比它小 - 如果后续还要用原数组顺序，记得备份——它是原地修改的
遇到重复元素时，std::nth_element 的行为是啥
它不区分“第 K 大”是按值还是按排名。比如数组 {5,5,5,4,3} 中，第 1、2、3 大都是 5；std::nth_element 会把某个 5 放到目标位置，但不承诺是“最左”还是“最右”的那个 5。
也就是说：结果值一定正确，但相同值之间的相对顺序不保证，也不保证你拿到的是第几个 5。
立即学习“C++免费学习笔记（深入）”；
- 如果你需要严格按“去重后第 K 大”，得先
std::set或std::unordered_set去重，再转回 vector 排序 - 如果只是统计频次或做 Top-K 输出，重复值不影响
nth_element结果的正确性 - 标准库不提供“第 K 个不重复值”的内置函数，必须自己处理
小数组（n < 20）或 K 极端偏移时，暴力法反而更稳
当 n 很小，或者 k == 1（找最大）、k == n（找最小）时，调 std::nth_element 的常数开销可能不如直接扫一遍：
// k == 1：直接 std::max_element auto it = std::max_element(nums.begin(), nums.end()); <p>// k == n：直接 std::min_element auto it = std::min_element(nums.begin(), nums.end());</p><p>// k <= 3 或 n <= 15：partial_sort 或手写三变量维护 top-k 更快</p>
-
std::partial_sort(nums.begin(), nums.begin() + k, nums.end(), std::greater<int>())</int>适合你要取前 k 个并排序的场景，但比nth_element慢一点 - 编译器对小数据的优化（如 unroll、SIMD）在暴力扫描中更容易生效
- 调试时看到一个简单循环，比跟踪
nth_element内部状态更直观
别用 std::sort + 下标访问来凑数
虽然 std::sort(nums.begin(), nums.end(), std::greater<int>()); return nums[k-1];</int> 能跑通，但浪费了至少一倍时间——你不需要整个数组有序，只需要一个位置的值。
- O(n log n) 对比 O(n)：当 n=1e6，实际耗时可能差 3–5 倍
- 内存局部性更差：
sort随机访问多，nth_element分区过程更接近顺序访问 - 如果数组是
const或不可修改，你还得额外拷贝一份，而nth_element同样要拷贝——这时才考虑std::vector临时副本 +nth_element
真正容易被忽略的是：很多人以为 nth_element 返回迭代器指向结果，其实它返回 void，你得自己取 *(it) 或下标访问。写错成 auto res = std::nth_element(...) 会编译失败。
