c++oding="utf-8" ?>
中位数应通过定位而非完整排序获取：奇数长度取第⌊n/2⌋小元素，偶数长度取第⌊n/2⌋−1和⌊n/2⌋小元素的平均值；推荐用std::nth_element（均摊o(n)）或手写quickselect，注意浮点转换与边界安全。
中位数定义决定你该不该排序
无序数组的中位数不是靠“找”出来的，而是靠“定位”出来的：长度为 n 的数组，中位数是第 ⌊n/2⌋ 小（0-indexed）的元素（奇数长度），或第 ⌊n/2⌋-1 和 ⌊n/2⌋ 小两数的平均值（偶数长度）。这意味着你不需要完整排序——只要知道某元素在全局顺序中的确切排名即可。
常见误区是直接调用 std::sort 再取中间索引，虽然能跑通，但时间复杂度是 O(n log n)，而实际有更优解。
用 std::nth_element 做部分排序
std::nth_element 是 C++ 标准库专为此类问题设计的算法：它将第 n 个位置（迭代器）置为“应该在此处”的元素，并保证其左侧所有元素 ≤ 它、右侧所有元素 ≥ 它。不保证左右子区间有序，但足够定位中位数。
实操建议：
- 对奇数长度
n，调用std::nth_element(v.begin(), v.begin() + n/2, v.end())，然后取v[n/2] - 对偶数长度
n，需分别定位第n/2-1和n/2小元素；注意不能连续两次nth_element而不重置范围——推荐先做一次到n/2，再对左半段做一次到n/2-1，或直接用std::partial_sort - 该函数平均时间复杂度
O(n)，最坏O(n²)（但实际实现如 libc++ / libstdc++ 多采用 introselect，有保障） - 会修改原数组；若不可修改，需先拷贝——此时空间开销
O(n)
手写快速选择（quickselect）应对定制需求
当标准库不可用（嵌入式）、需要确定性最坏性能、或要支持自定义比较逻辑且避免拷贝时，手写 quickselect 更可控。
关键点：
- 核心是 partition 操作：选 pivot，把数组划分为 ≤pivot / ≥pivot 两部分，返回 pivot 最终下标
- 若目标索引
k等于 pivot 下标，直接返回；小于则递归左半，大于则递归右半（减去左半长度） - 为避免最坏情况退化，pivot 推荐用「三数取中」或随机选取（
std::uniform_int_distribution） - 不要用递归过深的写法——改用 while 循环 + 显式栈模拟，防止栈溢出
示例片段（简化版）：
int quickselect(vector<int>& arr, int left, int right, int k) {
while (left <h3>别忽略浮点中位数和类型边界</h3>
<p>偶数长度时，两个中间值的平均值可能不是整数。如果数组是 <code>vector<int></int></code>，直接除以 <code>2</code> 会整除，必须显式转成浮点：</p>
<ul>
<li>错误写法：<code>(a + b) / 2</code>（整型截断）</li>
<li>正确写法：<code>(static_cast<double>(a) + b) / 2.0</double></code> 或 <code>0.5 * a + 0.5 * b</code>
</li>
</ul>
<p>另外注意：空数组无中位数，<code>n == 1</code> 时无需任何操作；<code>size_t</code> 类型做除法前务必转为有符号类型，否则 <code>n/2-1</code> 在 <code>n==0</code> 或 <code>n==1</code> 时会回绕成极大正数。</p>
<p>真正容易卡住的，往往不是算法本身，而是边界判断和类型转换那几行代码。</p></int>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
