std::nth_element是找中位数的首选，因其均摊o(n)、内置优化且规避最坏情况；需注意索引计算、容器可修改性及随机访问要求。
为什么 std::nth_element 是找中位数的首选
直接调用 std::nth_element 就能均摊 O(n) 找到中位数，不用手写 partition 循环或递归——它内部就是快速选择（Quickselect）的工业级实现，做了三数取中、小数组切片优化、尾递归消除，还规避了最坏 O(n²) 的常见坑。
常见错误是误用 std::sort 或 std::partial_sort：前者 O(n log n) 过重，后者在找单个中位数时仍做多余排序；还有人手动实现但忘了随机打乱，一遇到已排序数组就退化。
- 对偶数长度数组，中位数定义为第
n/2小（0-indexed），即std::nth_element(v.begin(), v.begin() + v.size()/2, v.end()) - 若需严格按数学定义（偶数时取中间两数平均），先取第
(n-1)/2和n/2小两个位置，再平均——注意两次调用std::nth_element会改变原数组顺序，应只调一次 + 一次扫描比较 - 输入容器必须支持随机访问迭代器（
std::vector、std::array可，std::list不可）
手写快速选择时必须加随机化 pivot
不随机选 pivot 的快速选择，在已排序或逆序数组上必退化成 O(n²)。C++ 标准库实现默认随机，但自己写时容易忽略这一步。
实操建议：用 std::random_device 和 std::mt19937 生成索引，交换到末尾再 partition；不要用 rand()（低质量、非线程安全）。
int quickselect(std::vector<int>& arr, int left, int right, int k) {
if (left == right) return arr[left];
std::random_device rd;
std::mt19937 g(rd());
std::uniform_int_distribution<int> dist(left, right);
std::swap(arr[dist(g)], arr[right]); // 随机换 pivot 到末尾
int pivot_idx = partition(arr, left, right);
if (k == pivot_idx) return arr[k];
else if (k <h3>
<code>std::nth_element</code> 的边界行为和 const 安全性</h3>
<p>它不保证“前 k 个元素有序”，只保证第 k 个位置放对了值，且左边 ≤ 它、右边 ≥ 它——这对中位数足够，但别指望它返回一个排好序的半数组。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>它会修改原容器，所以传入 <code>const std::vector<int>&</int></code> 编译失败；若原始数据不可改，必须先拷贝一份（<code>std::vector<int> copy = original;</int></code>），这点常被忽略导致运行时崩溃或静默错误。</p>
<ul>
<li>当 <code>k</code> 超出 <code>[0, size)</code> 范围，行为未定义（不是抛异常，是 UB）——务必检查 <code>k = size/2</code> 是否合法（空容器时 <code>size()==0</code>）</li>
<li>对于 <code>float</code> 或自定义类型，需确保 <code> 可用且满足 strict weak ordering；用 <code>std::nth_element(..., std::greater<int>{})</int></code> 可反向找第 k 大</code>
</li>
<li>在性能敏感场景（如高频调用），避免反复构造 vector 拷贝——可复用 buffer 或用 <code>std::span</code>（C++20）约束视图</li>
</ul>
<h3>中位数计算中容易被绕晕的索引细节</h3>
<p>中位数位置取决于“第几小”而非“下标是否居中”。例如 <code>{1,2,3,4}</code>（size=4），数学中位数是 <code>(2+3)/2=2.5</code>，对应第 2 小（index=1）和第 3 小（index=2）；而 <code>size/2</code> 是 2（0-indexed 下标），刚好是后者。但若误用 <code>(size-1)/2</code> 在奇数时又会错位。</p>
<p>统一做法：定义 <code>k1 = (size-1)/2</code>，<code>k2 = size/2</code>（整数除法），两者在奇数时相等，偶数时相邻——这样不用分支判断奇偶。</p>
<ul>
<li>奇数长度：<code>std::nth_element(v.begin(), v.begin() + v.size()/2, v.end())</code> 后取 <code>v[v.size()/2]</code>
</li>
<li>偶数长度：必须分别获取 <code>v[(size-1)/2]</code> 和 <code>v[size/2]</code>，不能只调一次 <code>nth_element</code> 然后读两个位置——因为 partition 后只有目标位置确定，邻位不保序</li>
<li>用 <code>std::vector::data()</code> + <code>std::nth_element</code> 可避免迭代器开销，尤其对大数组</li>
</ul>
<p>实际项目里，95% 的中位数需求用 <code>std::nth_element</code> 加两行索引逻辑就够了；手写快速选择只在需要完全控制 pivot 策略、或嵌入式环境无 STL 时才值得投入。真正难的是把索引算对，而不是算法本身。</p></int></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
