std::nth_element比手写快排分区更稳，因其复用libc++/libstdc++高度优化的内省式分区逻辑，自动切堆选或插入排序，避免o(n²)退化；手写易误成全量排序。
std::nth_element 为什么比手写快排分区更稳
它直接复用 libc++ 或 libstdc++ 高度优化的内省式分区逻辑，内部会自动切到堆选择或插入排序小数组，避免最坏 O(n²)。你自己写 partition + 递归调用，稍不留神就退化成全量排序。
实操建议：
- 只要求第 k 小（或第 k 大）元素值，或只要求“前 k 个无序但不超第 k 小”，就无条件优先用
std::nth_element - 注意：它只保证迭代器位置
nth指向的元素就位，左边 ≤ 它、右边 ≥ 它，但左右子区间不排序 - 若需严格升序的前 k 个，得再对前 k 位调用
std::sort，别指望nth_element替你排好
std::partial_sort 和 std::nth_element 选哪个
看你要的是“有序 Top K”还是“仅定位第 K”——前者用 std::partial_sort，后者用 std::nth_element。两者时间复杂度都是平均 O(n log k)，但常数差一倍以上。
常见错误现象：std::partial_sort 被误用于只取最大值场景，结果多花 log k 倍时间做无谓排序。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 要前 k 个升序排列 → 用
std::partial_sort(begin, begin + k, end) - 只要第 k 小的值，或只要前 k 个“乱序但都 ≤ 第 k 小” → 用
std::nth_element(begin, begin + k - 1, end)（注意索引是 k−1） - 如果 k 接近 n（比如 k > n/2），
std::nth_element仍稳定；而partial_sort此时实际接近全排序，不如直接sort+ 截断
自己实现快速选择时最容易崩的三个点
不是算法逻辑错，而是边界和 pivot 选法翻车。
常见错误现象：数组越界、死循环、返回错误下标、在重复元素多时性能骤降。
实操建议：
- 分区函数必须严格保证：返回位置
p满足[l, p)≤ pivot，(p, r]≥ pivot，且p必须落在[l, r]内——很多手写版本漏处理l == r或单元素 case - 别用
arr[l]当 pivot：遇到已排序数组直接 O(n²)；改用三数取中或arr[l + rand() % (r - l + 1)] - 递归调用时，检查新区间是否合法：
if (l >= r) return必须有，且左右分支范围要严格对应分区结果，比如左半段是[l, p)就别传[l, p]
Top K 在 vector 和 vector> 场景下的写法差异
核心区别在比较逻辑怎么塞进去，而不是算法本身变。
使用场景：数值型直接比大小；结构体或自定义类型必须显式指定按哪个字段比，否则编译不过或行为未定义。
实操建议：
- 对
vector<int></int>，nth_element(v.begin(), v.begin() + k, v.end())直接可用 - 对
vector<pair string>></pair>，必须传比较器：nth_element(v.begin(), v.begin() + k, v.end(), [](auto& a, auto& b) { return a.first - 如果要按第 k 大，比较器里写
a.first > b.first，别去 reverse 容器——nth_element不依赖全局顺序 - lambda 捕获为空即可，不要捕获外部变量，否则可能隐式转成非 trivial 类型，影响性能
真正卡住人的往往不是算法原理，而是 nth_element 的迭代器语义、pivot 选取策略、以及自定义类型时比较器的 const 引用写法——这三个地方写错，调试时连崩溃点都难定位。
