std::nth_element 是求中位数最高效方法，平均 o(n) 时间复杂度；奇数长度直接取第 ⌊n/2⌋ 小元素，偶数长度需两次调用分别定位中间两元素，小数组（≤10）建议手写或用 std::sort 配合编译器优化。
用 std::nth_element 一次性找到中位数，不排序
中位数本质是第 ⌊n/2⌋ 小（或中间两个的平均），不需要全数组有序。直接调 std::nth_element 是最常用且高效的做法，平均时间复杂度 O(n)，远优于 std::sort 的 O(n log n)。
注意它只保证第 k 个位置放对了元素，左边 ≤ 它、右边 ≥ 它，但左右各自无序 —— 这刚好够用，省下大量开销。
常见错误：传错索引。比如 arr 有 5 个元素，中位数是第 3 小（0-indexed 第 2 位），不是第 3 位；偶数长度时需取 nth_element 两次（或一次后手动访问两个位置）：
std::vector<int> arr = {3, 1, 4, 1, 5};
std::nth_element(arr.begin(), arr.begin() + 2, arr.end()); // 索引 2 → 第 3 小
int median = arr[2]; // 3</int>
偶数长度时怎么安全取两个中间值
当数组长度为偶数，中位数是中间两数的平均值，但 std::nth_element 不保证这两个位置都“就位”。不能只调一次然后读 arr[n/2-1] 和 arr[n/2] —— 后者可能还没被正确放置。
稳妥做法分两步：
- 先用
std::nth_element把第n/2 - 1小元素放到索引n/2 - 1 - 再在右半段（
arr.begin() + n/2到末尾）里找最小值，即第n/2小
或者更简单：直接调两次 std::nth_element，第二次作用于整个数组，目标索引为 n/2（注意第一次调用会打乱顺序，所以要么备份，要么重排）：
std::vector<int> arr = {2, 1, 4, 3};
int n = arr.size();
std::nth_element(arr.begin(), arr.begin() + n/2 - 1, arr.end());
std::nth_element(arr.begin(), arr.begin() + n/2, arr.end());
double median = (arr[n/2 - 1] + arr[n/2]) / 2.0;</int>
小数组或嵌入式场景下，手写三数取中+部分排序更稳
std::nth_element 底层是 introselect（快选 + 堆选 + 插入排序兜底），常数较大。若数组固定很小（如 ≤ 10），手写逻辑反而更快、更可控，也避免 STL 迭代器开销和内存分配。
例如 5 个数的中位数，只需最多 6 次比较就能确定，比调库还轻量：
// 简化版：对长度为 5 的数组，返回中位数
int median5(int a, int b, int c, int d, int e) {
// 三数取中选 pivot，再做少量交换...
// 实际可用 std::array<int> + std::sort(arr.begin(), arr.end()) —— 编译器对小数组会优化成展开比较
}</int>
关键点：
- 编译器对
std::sort在std::array上常做模板特化，小尺寸下实际生成的是 if-else 比较树 - 不要为 3~7 个元素引入
std::nth_element，它要构造迭代器、检查随机访问、调用函数对象，得不偿失
使用 std::partial_sort 的适用边界在哪
std::partial_sort 适合你需要“前 k 小且有序”时，比如找 Top-K + 同时要中位数。但它时间复杂度是 O(n log k)，当 k ≈ n/2（即求中位数），就退化到接近 O(n log n)，不如 nth_element。
典型误用场景：
- 只为了取中位数而写
std::partial_sort(arr.begin(), arr.begin()+mid, arr.end()) - 认为“partial 就一定比 full 快”——其实当 k > n/4 左右，
nth_element的常数优势就很明显了
只有当你后续还要用前一半的有序性（比如打印前 3 小的数并取其中位），才值得换用 partial_sort。
真正容易被忽略的是：中位数定义依赖于数据是否可修改。如果原数组不能动，nth_element 就必须拷贝一份 —— 这个拷贝成本有时比算法本身还高；此时若允许额外 O(n) 空间，用 std::vector 拷贝后处理，比反复调用带自定义 comparator 的复杂方案更可靠。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
