c++oding="utf-8" ?>
优先使用 std::nth_element，因其平均 O(n)、最坏不退化、内置优化且无需手动打乱；手写仅适用于需自定义逻辑等特殊场景。
为什么 std::nth_element 比手写快排划分更值得优先用
直接结论：除非你明确需要自己控制划分逻辑（比如处理自定义比较、避免递归栈溢出、或做教学演示），否则别手写快速选择——std::nth_element 是经过高度优化的工业级实现，平均时间复杂度 O(n)，常数因子远小于朴素实现，且对重复元素、已排序输入等边界情况做了充分适配。
它底层不一定是纯快排划分；GCC libstdc++ 用的是 introselect（快排 + 堆 + 中位数中位数 fallback），Clang libc++ 类似。这意味着：即使最坏输入，它也不会退化到 O(n²)。
- 调用前无需手动随机打乱数组，
std::nth_element内部已处理 - 它只保证第 k 个位置放好目标值，左侧 ≤ 它、右侧 ≥ 它，但不排序左右子段
- 注意索引：找“第 K 大”，对应的是
nth_element(..., begin + k - 1, ...)吗？不是——得先转成“第 (n−k+1) 小”
手写快速选择时，pivot 选错就直接 O(n²)
常见错误是固定取 arr[left] 或 arr[right] 当 pivot。面对已排序数组（升序/降序）或大量重复值，划分极不均衡，递归深度达 O(n)，每次划分 O(n)，总耗时 O(n²)。
必须引入随机化或三数取中：
- 推荐方案：用
std::random_device和std::mt19937随机选一个下标rand_idx，swap 到末尾再做 partition - 简单替代：取
left、mid、right三者中位数作为 pivot，能显著缓解有序输入问题 - 别在 partition 函数里用
std::swap对原生指针或内置类型——直接写std::iter_swap或裸赋值更高效
第 K 大 ≠ 直接传 k 给 quickselect
快速选择算法默认解决“第 k 小”问题。要找第 K 大，必须做坐标转换。容易漏掉的点：
- 假设数组长度为
n，升序排列下第 1 大是arr[n-1]，即第n小；第 K 大就是第n - k + 1小 - 若 k 超出范围（如 k ≤ 0 或 k > n），
std::nth_element行为未定义，需提前校验 - 示例：对
{3,2,1,5,6,4}（n=6），找第 2 大 → 找第6-2+1 = 5小 → 调用nth_element(v.begin(), v.begin()+4, v.end())
partition 实现里边界条件一错全崩
手写 Lomuto 或 Hoare 分区时，while 循环的终止条件、交换时机、最终 pivot 归位下标，三处任一出错都会导致死循环或越界访问。
以 Lomuto 为例（更易理解但稍慢）：
int partition(vector<int>& arr, int left, int right) {
int pivot = arr[right]; // 先确保 pivot 是合法下标
int i = left;
for (int j = left; j <ul>
<li>循环内 <code>j ，不是 <code> —— 否则会把 pivot 自己也参与比较</code></code>
</li>
<li>if 条件用 <code> 而非 <code>，否则相同值可能被错误分到右侧，影响 k 的定位精度</code></code>
</li>
<li>返回值必须是 pivot 归位后的下标，后续递归要用它切分区间</li>
</ul>
<p>实际项目里，只要标准库可用，就用 <code>std::nth_element</code>；真要手写，重点盯住 pivot 选取策略和 partition 边界——这两处出错，性能和正确性同时崩盘。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
