std::nth_element是C++中查找第k小元素的最优工具，平均时间复杂度O(n)，仅重排容器使第k位正确、左右满足划分性质，不保证内部有序；使用时需检查k有效性并手动取v[k]。
std::nth_element 是 C++ 里最快的“找第 k 小”工具
它不排序整个容器，只保证第 k 个位置放对了数，左边 ≤ 它、右边 ≥ 它。平均时间复杂度 O(n)，比 std::sort 的 O(n log n) 快得多，尤其当只要一个中位数或 Top-K 中的某一个值时。
常见错误是误以为它返回第 k 小的值——其实它只重排容器，你要自己取 v[k]（注意下标从 0 开始）。
-
std::nth_element(v.begin(), v.begin() + k, v.end())：最常用形式，k 是目标位置索引 - 支持自定义比较器，比如找第 k 大：
std::nth_element(v.begin(), v.begin() + k, v.end(), std::greater<int>())</int> - 若容器为空或
k >= v.size()，行为未定义——调用前必须检查 - 它不保证左右两段内部有序，仅满足划分性质；别指望它替代
partial_sort来拿前 K 个有序元素
什么时候该用 nth_element 而不是 partial_sort 或 sort
核心判断依据：你是否只需要“第 k 个值本身”，而不是“前 k 个有序结果”。
- 要中位数？→ 用
nth_element，快且省内存 - 要 Top-10 排好序的用户？→ 用
partial_sort，nth_element不提供顺序保证 - 要全部排序后再取第 k 个？→ 直接
nth_element，省掉多余O(n log n)开销 - 数据量大（比如百万级 vector）且 k 很小（如 k=0 找最小值）？
nth_element仍稳定O(n)，而min_element是O(n)但更轻量；此时可权衡：若只找最小/最大，优先用min_element/max_element
手写快速选择（QuickSelect）的必要场景
标准库 nth_element 已高度优化，99% 场景够用。只有在以下情况才考虑手写：
立即学习“C++免费学习笔记（深入）”；
- 需要严格控制 pivot 选取策略（比如强制中位数的中位数避免最坏
O(n²)） - 处理自定义数据结构且无法用迭代器适配（如稀疏数组、外部存储索引）
- 嵌入式环境禁用 STL 算法，或需确定性最坏性能（
nth_element标准未规定最坏复杂度，实际实现多为 IntroSelect，但不可依赖） - 调试或教学目的——这时注意：递归版易栈溢出，务必转成迭代；partition 逻辑必须和
std::partition一致（即[left, i)≤ pivot，[i, right)≥ pivot）
容易被忽略的边界与陷阱
这些点不报错，但结果错得悄无声息：
-
k是无符号类型（如size_t）时，k-1可能绕成极大正数 → 检查k 前先确保 <code>k非负 - 传入
std::list迭代器？不行。nth_element要求随机访问迭代器，list::iterator不满足 → 改用vector或手写基于链表的 partition - 自定义类型没定义
operator<或比较器漏 const 引用？编译失败，但错误信息常指向内部模板深处 → 先单独测试比较逻辑 - 多线程读写同一容器？
nth_element会修改原容器 —— 若需并发安全，要么加锁，要么复制后操作
真正难的不是写对算法，而是判断“我此刻到底要不要它”。中位数、P95 延迟、异常值检测……这些场景里，nth_element 往往是那个被低估的默认选项。
