c++oding="utf-8" ?>
std::nth_element 通常比手写快，因其采用三数取中、插入排序兜底、尾递归消除和小数组优化；手写需用 Hoare 分区、随机化 pivot 并正确处理边界与递归分支。
快速选择算法在平均情况下确实能达到 O(n) 时间复杂度，但实际写 C++ 时，直接手写 partition 很容易退化成 O(n²)，尤其遇到重复元素多或已排序数据——这不是理论错，是实现细节没控住。
为什么 std::nth_element 通常比手写快？
标准库实现（如 libstdc++）对 std::nth_element 做了多重优化：三数取中 + 插入排序兜底 + 尾递归消除 + 小数组切片优化。手写若只套教科书版 Lomuto 分区，std::vector 全是相同值时每次 pivot 都卡在端点，立刻 O(n²)。
- 用
std::nth_element查第 K 大，要传begin() + k - 1（从 0 开始），且注意它是查第 K 小；查第 K 大可改传end() - k或先 reverse - 若必须手写，推荐 Hoare 分区（交换更少、边界更稳），且 pivot 必须随机化：
std::swap(arr[l], arr[l + rand() % (r - l + 1)]) - 递归调用前加长度判断：子区间
r - l + 1 时直接插入排序，避免小数组的递归开销和退化风险
查第 K 大数的正确索引怎么算？
很多人在这里翻车：C++ 容器默认升序，std::nth_element(v.begin(), v.begin() + k - 1, v.end()) 找的是第 K 小；要第 K 大，得把迭代器偏移设为 v.end() - k，前提是 k 合法（1 ≤ k ≤ v.size()）。
- 错误写法：
nth_element(v.begin(), v.begin() + k, v.end())→ 索引越界或语义反了 - 安全写法：
auto it = v.begin(); std::nth_element(it, it + (v.size() - k), v.end())，这样*(it + (v.size() - k))就是第 K 大 - 如果输入是
vector且不允许修改原数组，务必先拷贝：& nums vector，否则tmp = nums nth_element会重排原容器
手写快速选择时最容易漏掉的三个检查
不加这些，本地测例过不了，线上一跑大数据就崩：
-
k越界检查：if (k arr.size()) throw std::out_of_range("k out of range") - 分区后 pivot 位置计算必须用实际返回的索引，不是固定公式：Hoare 分区返回的是左段右边界，Lomuto 返回的是 pivot 最终位置，二者参与比较的逻辑不同
- 递归分支不能无脑进：比如 pivot_pos == target 时直接返回；pivot_pos > target 时只递归左半段；pivot_pos pivot_pos + 1，否则死循环
真正难的不是写出 O(n) 的伪代码，而是让 pivot 选得稳、边界缩得准、重复值压得住。生产环境建议优先用 std::nth_element，除非 profiling 明确指出它成了瓶颈，再考虑定制化手写——而且得配上随机 pivot + 小数组 fallback + 迭代替代递归。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
