std::nth_element是部分重排算法，平均o(n)找第k小元素；求第k大需转为第(size-k)小，最坏o(n²)但极少触发，不保证子区间有序，仅保证左右分区与基准值的大小关系。
std::nth_element 是什么，它真能 O(n) 找第 k 大元素？
它不是排序函数，也不是堆；它是部分重排容器的算法，保证第 nth 位置放的是“如果全排好后该在那儿”的值——也就是第 k 小（或大）的元素。平均时间复杂度确实是 O(n)，但最坏是 O(n²)，实际中极少触发，别被教科书吓住。
注意：它不保证前后子区间有序，只保证 [begin, nth) 全 ≤ *nth，(nth, end] 全 ≥ *nth。你要第 k 大？得把索引转成“第 (size - k) 小”再调用。
- 想取第 1 大（最大值）：
nth = v.begin() + v.size() - 1 - 想取第 3 大：
nth = v.begin() + v.size() - 3，前提是v.size() >= 3 - 越界没检查！
v.size() 时直接 UB，必须自己兜底
为什么不用 std::sort 或 std::partial_sort？
std::sort 是 O(n log n)，全排完再取 v[k-1] 太重；std::partial_sort 虽然也 O(n log k)，但它会把前 k 个**排好序**，而你往往只需要第 k 个值本身——多出来的排序纯属浪费。
对比实测（1e6 随机 int，找第 100 大）：nth_element 通常比 partial_sort 快 2–3 倍，比 sort 快 5 倍以上。但如果你后续还要用前 k 个的有序结果，那就该换 partial_sort。
立即学习“C++免费学习笔记（深入）”；
-
nth_element：只要值，不要顺序 → 推荐 -
partial_sort：要前 k 个且需升序排列 → 合理选择 -
priority_queue：流式数据、k 很小、内存受限 → 另一思路，但常数大
常见错误：索引算错、迭代器失效、没处理重复值
最典型翻车点：把“第 k 大”直译成 v[k-1]，结果拿到的是第 k 小。C++ 标准库所有 nth 系列都按升序语义设计，nth_element 的 nth 指的是“升序下第 n 个位置”，不是“第 n 大”。
- 正确换算：第 k 大 → 升序下索引
v.size() - k，然后传v.begin() + v.size() - k - 容器为空或
k > v.size()时，v.begin() + v.size() - k会越界，必须提前判断 - 有重复值？没问题。
nth_element仍能正确放置一个合法的第 k 大值（比如数组全是 5，第 3 大还是 5） - 别在
nth_element后假设v[0]是最小值——它可能不是，只保证 ≤*nth
实际写法：带边界检查的封装示例
别每次手写索引换算和检查。一个小工具函数能省掉 80% 的坑：
int get_kth_largest(std::vector<int>& v, size_t k) {
if (k == 0 || k > v.size()) throw std::out_of_range("k out of range");
auto nth = v.begin() + v.size() - k;
std::nth_element(v.begin(), nth, v.end());
return *nth;
}
注意：这个函数会修改原容器顺序。如果不能破坏原数据，得先 std::vector<int> copy = v</int> 再操作。空间开销 O(n)，但比全排序省时；若只读场景多，考虑建堆或用 std::span 配合临时 buffer。
真正容易被忽略的是：它不提供稳定排序保证，相同值的相对位置可能变；如果你依赖原始顺序中“第一个出现的第 k 大值”，nth_element 不满足——得换扫描+堆或计数法。
