中位数应通过定位而非完整排序获取：奇数长度取第⌊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 个位置（迭代器）置为“应该在此处”的元素，并保证其左侧所有元素 ≤ 它、右侧所有元素 ≥ 它。不保证左右子区间有序，但足够定位中位数。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 对奇数长度
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 < right) {
int p = partition(arr, left, right);
if (p == k) return arr[p];
if (k < p) right = p - 1;
else left = p + 1;
}
return arr[left];
}
别忽略浮点中位数和类型边界
偶数长度时，两个中间值的平均值可能不是整数。如果数组是 vector<int>，直接除以 2 会整除，必须显式转成浮点：
- 错误写法：
(a + b) / 2（整型截断） - 正确写法：
(static_cast<double>(a) + b) / 2.0或0.5 * a + 0.5 * b
另外注意：空数组无中位数，n == 1 时无需任何操作；size_t 类型做除法前务必转为有符号类型，否则 n/2-1 在 n==0 或 n==1 时会回绕成极大正数。
真正容易卡住的，往往不是算法本身，而是边界判断和类型转换那几行代码。
