std::nth_element是首选，因其为工业级快速选择实现，平均O(n)、最坏O(n²)，经三数取中和插入排序等优化；手写易在pivot选择、分区细节和递归转换出错，且难防恶意输入导致性能退化。
为什么 std::nth_element 是首选，而不是手写快选
标准库的 std::nth_element 就是快速选择算法的工业级实现，平均 O(n)、最坏 O(n²)，且经过大量优化（比如三数取中、小数组切分用插入排序）。自己重写容易在边界、pivot 选择、递归/迭代转换上出错，还可能更慢。
除非你在面试中被明确要求手写，或需定制 pivot 策略（如强制随机化防恶意输入），否则直接用它更稳妥。
- 头文件只需
#include <algorithm> - 调用形式：
std::nth_element(begin, begin + k, end)—— 注意：它把第k小元素放到位置begin + k，不是第k大 - 若要找第
K大，等价于找第n - K小（0-indexed），即传入迭代器位置v.begin() + n - K
手写快选时 pivot 选错会导致 O(n²) 退化
最常见错误是固定取首/尾元素作 pivot，遇到已排序或逆序数组就会触发最坏情况。哪怕数据看似随机，攻击者也可能构造输入让性能崩塌。
必须引入随机性或更鲁棒策略：
立即学习“C++免费学习笔记（深入）”；
- 推荐：
std::random_device+std::uniform_int_distribution随机选下标，swap 到末尾再 partition - 次选：三数取中（取首、中、尾三值的中位数），但对特定模式仍可能失效
- 避免：每次无脑取
left或right—— 这在 LeetCode 测试用例里大概率超时
示例关键片段：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
int rand_idx = left + dist(gen) % (right - left + 1); std::swap(arr[rand_idx], arr[right]); // 把随机 pivot 换到最后
partition 实现细节决定是否越界或漏元素
经典 Lomuto 分区法（单指针扫描）写错一个条件就崩：比如用 <= pivot 而不是 < pivot，会导致 pivot 自身被重复交换；或者循环结束没把 pivot 放回正确位置。
更稳的是 Hoare 分区（双指针向中间靠拢），但要注意：
- 两个指针必须至少走一步，否则在
left == right时死循环 - 返回的是「右半区起点」，不是 pivot 最终索引，后续递归范围要对应调整
- 分区后不能假设
arr[i]就是 pivot 值 —— 它可能已被交换过多次
别依赖“分区后 pivot 在最终位置”这个直觉来写递归终止条件，应严格比较 pos 与目标索引 k 的大小关系。
迭代版比递归版更安全，但要注意栈模拟逻辑
递归写法简洁，但深递归可能爆栈（尤其 worst-case 时递归深度达 n）。改成迭代需手动维护待处理区间，常见错误是：
- 只 push 了左半段或右半段，漏掉另一个分支
- push 顺序反了，导致非尾递归语义（虽不影响结果，但失去空间优势）
- 用
std::stack<std::pair<int,int>>存区间时，忘记检查left < right就直接 push，引入无效区间
真正省栈空间的关键，是每次只压入一个子区间（类似尾递归优化）：先处理较小一半，再用循环处理较大一半。但这会增加代码复杂度，日常建议直接用递归 + 随机 pivot，99% 场景够用。
边界和 pivot 随机化这两点，比算法名字里的“快速”更重要——没处理好，O(n) 就只是个幻觉。
