std::nth_element是找中位数的首选，因其均摊O(n)、内置三数取中等优化；奇数长度取索引(n-1)/2，偶数长度需两次调用或特殊处理；注意迭代器要求、比较器语义及溢出风险。
为什么 std::nth_element 是找中位数的首选
直接调用 std::nth_element 就能均摊 O(n) 找到中位数，不用自己手写分区逻辑。它底层就是快速选择（Quickselect）的优化实现，做了三数取中、小数组切回插入排序等工程优化，比裸写递归或迭代版本更稳。
常见错误是误用 std::sort 或 std::partial_sort：前者是 O(n log n)，后者在找单个位置时也多做无用功；还有人手动实现但忘了处理重复元素导致死循环。
- 对奇数长度数组，中位数是第
(n-1)/2个索引（0-based） - 对偶数长度，严格中位数需两个中间值平均，但
std::nth_element只能一次定位一个位置；若只需下中位数（lower median），取索引n/2 - 1；上中位数（upper median）取n/2 - 必须传入随机访问迭代器，
std::list等不支持
手写快速选择时怎么避免最坏 O(n²) 退化
核心是 pivot 选取不能固定（比如总选首/尾），否则已排序数组会触发最差性能。工业级做法是「三数中值法」：取首、中、尾三个元素排序后取中间值作 pivot；更稳妥可加随机扰动，比如 std::shuffle 首尾小段，或直接 std::uniform_int_distribution 随机选一个下标交换到末尾。
另一个关键点是分区后要明确收缩区间：当 pivot 最终落点 pos 大于目标索引 k，只递归左半段；小于则递归右半段（注意右半段新 k 要减去左段长度+1）。
立即学习“C++免费学习笔记（深入）”；
- 别用递归过深——数据量大时栈溢出风险高；改用 while 循环 + 显式更新
left/right边界 - 小数组（如 size ≤ 10）直接插排，比递归开销小
- 分区函数必须保证 pivot 左侧 ≤ pivot、右侧 ≥ pivot，且返回的是 pivot 的最终下标（不是比较次数）
std::nth_element 的实际调用姿势和陷阱
它不保证其余元素有序，只确保第 k 个位置是正确值，且左边元素 ≤ 它、右边 ≥ 它。这个语义刚好够找中位数，但如果你顺手打印前几个元素想“验证排序”，会发现它们乱序——这不是 bug，是设计如此。
典型误用：std::nth_element(v.begin(), v.begin() + k, v.end(), std::greater<int>())</int> 想找第 k 大，却忘了比较器改变的是“序”的定义，此时中位数对应的位置索引也要反向计算（比如第 k 大 = 第 n-k-1 小）。
- 调用前确认容器非空，否则
v.begin() + k可能越界 - 迭代器范围必须合法：
first ≤ nth ≤ last，否则未定义行为 - 自定义类型需提供满足严格弱序的比较器，且不能在比较中修改对象状态
偶数长度时中位数的两种处理路径
标准数学定义的中位数在偶数长度时是中间两数平均值，但 std::nth_element 一次只能定住一个位置。可行方案有两个：
- 调用两次：
std::nth_element先定位n/2 - 1，再对右半段（从n/2开始）调用找最小值，或者再调一次找n/2；但第二次调用范围变小，整体仍是均摊O(n) - 更高效：用一次
std::nth_element把数组划成三块——左段（≤ lower median）、pivot 区（含所有等于中位候选的值）、右段（≥ upper median），然后扫描 pivot 区找上下界；适合有大量重复值的场景 - 如果业务允许近似（如数据流中位数），可考虑
std::priority_queue维护双堆，但那是O(n log n)，和本题目标不同
真正容易被忽略的是：浮点平均可能引入精度误差，而整数除法会截断；(a + b) / 2.0 和 static_cast<double>(a + b) / 2</double> 行为不同，尤其当 a + b 溢出时。
