c++oding="utf-8" ?>
std::nth_element是找中位数最稳妥的选择，因其平均o(n)、防退化、经充分测试；需注意索引范围、容器要求及偶数长度时的双值处理。
为什么 std::nth_element 是找中位数最稳妥的选择
直接用 std::nth_element 就行，它在标准库中已实现平均 O(n) 的快速选择逻辑，且经过充分测试和优化。自己手写 partition + 递归容易出边界错误、栈溢出或退化成 O(n²)，尤其在重复元素多或已排序输入下——而 std::nth_element 内部通常采用 introselect（快选 + 堆选兜底），能自动避免最坏情况。
使用场景：只需一个值（如中位数），不关心其余元素是否有序；数组可修改；C++11 及以上。
常见错误现象：std::nth_element(v.begin(), v.begin() + k, v.end()) 后访问 v[k] 却得到错误值——原因常是 k 超出范围（比如对空容器取中位数，或奇偶长度没区分好索引）。
- 对大小为
n的容器，中位数位置是n/2（向下取整），即第n/2 + 1小的元素（0-indexed 下索引为n/2） - 若需「严格中位数」（偶数长度时取中间两数平均），
std::nth_element只能帮你拿到两个候选值之一，得额外调用两次或改用std::partial_sort - 传入的迭代器必须满足
RandomAccessIterator要求（vector、deque可以，list不行）
手写快速选择时怎么防退化和越界
如果非要自己实现（比如教学、嵌入式无 STL 场景），核心是三点：三数取中选 pivot、尾递归优化、小数组切分后插入排序兜底。否则遇到升序数组时每次 pivot 都选最小值，立刻退化成 O(n²)。
关键参数差异：left 和 right 是闭区间（[left, right]），而 std::nth_element 的第三个参数是 end 迭代器（开区间）。手写时若混淆，极易导致死循环或访问 arr[right+1]。
示例片段（简化版，仅示意逻辑）：
int quickSelect(vector<int>& arr, int left, int right, int k) {
if (left == right) return arr[left];
int pivotIdx = partition(arr, left, right);
if (k == pivotIdx) return arr[k];
else if (k <p>注意：<code>partition</code> 必须保证返回的 <code>pivotIdx</code> 处的值恰好是该子数组的 pivot 本身，且左侧 ≤ pivot、右侧 ≥ pivot；否则 <code>k</code> 的比较逻辑会错乱。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill2659" title="C++"><img
src="https://img.php.cn/upload/skill/000/000/081/178927213426672.jpg" alt="C++" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill2659" title="C++" class="overflowclass">C++</a>
<p class="overflowclass">"空空如也"</p>
</div>
<a rel="nofollow" href="/xiazai/skill2659" title="C++" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<h3>
<code>std::nth_element</code> 在 vector 和 array 上的性能实测差异</h3>
<p>对 <code>std::vector<int></int></code>，<code>std::nth_element</code> 平均耗时稳定在 O(n)，实测百万元素约 3–5ms（Clang/GCC -O2）；对 <code>std::array<int n></int></code>，由于 size 固定且栈上分配，编译器可能做更多内联优化，快 10–15%，但差别不大。</p>
<p>真正影响性能的是数据局部性：连续内存（<code>vector</code>）远优于指针数组（<code>vector<int></int></code>）；若元素类型大（如 <code>string</code>），移动成本高，建议传 <code>vector<size_t></size_t></code> 索引再间接访问，而非直接对对象排序。</p>
<p>兼容性注意点：</p>
<ul>
<li>C++17 起支持执行策略（如 <code>std::nth_element(std::execution::par, ...)</code>），但并行版本不保证稳定性，且 GCC libstdc++ 目前对 <code>par</code> 实现较弱，慎用</li>
<li>MSVC 对小数组（<code>n ）会自动切到插入排序，GCC 则倾向用 median-of-3 + 插入排序混合策略</code>
</li>
<li>若容器含自定义比较器，确保其满足 strict weak ordering，否则行为未定义</li>
</ul>
<h3>偶数长度时取「数学中位数」的可靠写法</h3>
<p>标准库没有一键求双中位数的函数，必须分两步：先用 <code>std::nth_element</code> 找第 <code>n/2 - 1</code> 和 <code>n/2</code> 小的两个位置，但不能直接两次调用——第一次会打乱数组，第二次结果无效。</p>
<p>正确做法只有两种：</p>
<ul>
<li>用 <code>std::partial_sort</code> 排前 <code>n/2 + 1</code> 个元素（代价 O(n log k)，k = n/2+1），然后取 <code>arr[n/2-1]</code> 和 <code>arr[n/2]</code>
</li>
<li>手写一次 partition 得到两个候选值：先找第 <code>n/2</code> 小（pivotIdx），再在左半部分找最大值、右半部分找最小值（即 <code>max(arr[left..pivotIdx-1])</code> 和 <code>min(arr[pivotIdx+1..right])</code>），但代码量翻倍且易错</li>
</ul>
<p>实践中，除非 n 极大且对延迟极度敏感，否则优先选 <code>partial_sort</code> —— 它语义清晰、STL 保证正确性，且现代 CPU 对小规模 log n 分支预测很友好。</p>
<p>最容易被忽略的一点：中位数定义本身依赖于数据是否可重复、是否允许浮点除法。用 <code>int</code> 存储时，<code>(a + b) / 2</code> 可能溢出，应写成 <code>a + (b - a) / 2</code> 或转 <code>long long</code> 再算。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
