std::nth_element 更稳因其多重优化：小数组用插入排序、三数取中选基准、尾递归消除，避免最坏O(n²)；手写易退化，应优先使用它。
为什么 std::nth_element 通常比手写快排分区更稳？
因为标准库实现做了多重优化：小数组用插入排序、三数取中选基准、尾递归消除、避免最坏 O(n²)。手写时若只按教科书方式递归调用，遇到已排序数组或大量重复元素极易退化。
实操建议：
- 优先用
std::nth_element，它保证平均 O(n)，且不改变其余元素相对顺序（只确保第 k 位正确） - 若需原地、无额外空间，且明确要求“第 K 大”（非第 K 小），注意传入反向迭代器或调整索引：
std::nth_element(v.begin(), v.begin() + k - 1, v.end(), std::greater()) - 不要自己实现递归版本却忘了加随机化——
std::random_shuffle已弃用，改用std::shuffle(v.begin(), v.end(), std::mt19937{std::random_device{}()})
手写快速选择时，partition 函数的边界怎么写才不出错？
经典错误是左右指针越界、交换后没移动、或对重复值处理不当，导致死循环或结果错位。关键不是“怎么分”，而是“分完后 pivot 落在哪”。
实操建议：
- 用 Lomuto 分区时，返回的是 pivot 最终下标，但必须确保该位置值就是 pivot 值（即 swap 后再返回
store_idx） - 用 Hoare 分区更高效，但返回值不是 pivot 位置，而是左段右边界；需额外判断
left和right是否交叉，不能直接拿返回值当 pivot 下标 - 对重复值，推荐用三路分区（
lt/gt双指针），否则在全相同数组上会退化成 O(n²)
第 K 大 vs 第 K 小：索引转换和比较函数容易漏哪？
很多人写完发现结果是第 K 小，却以为逻辑错了——其实只是没转译“大”和“小”的语义。C++ 默认升序，nth_element 找的是升序下第 k 个（即第 k 小）。
实操建议：
- 找第 K 大 → 等价于升序数组中找索引为
n - k的元素（0-indexed），即调用std::nth_element(v.begin(), v.begin() + n - k, v.end()) - 或保持索引不变，改比较逻辑：
std::nth_element(v.begin(), v.begin() + k - 1, v.end(), std::greater，此时 k 是 1-indexed()) - 切勿混用：比如用
greater却还传n - k，会导致越界或错位
平均时间复杂度 O(n) 的“平均”到底依赖什么？
不是指“多次运行取平均”，而是指对所有输入排列等概率假设下的期望时间。实际中若数据有偏（如部分有序、大量重复），性能可能接近 O(n log n)，甚至 O(n²)（未随机化时）。
实操建议：
- 测试时别只用 sorted 数组，加一组
std::shuffle后再测，否则看不到真实均摊表现 - 用
std::chrono::high_resolution_clock测单次耗时意义不大；应测 100+ 次取中位数，排除系统抖动 - 当 n
真正难的不是写出能跑通的版本，而是让 partition 在重复值、边界值、空输入、k 越界这些边缘情况都稳定返回有效下标——这些地方不加断言或单元测试，上线后很难复现。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
