C++怎么求中位数 C++中nth_element函数用法【算法】

nth_element求中位数最快但需分奇偶处理：奇数取v[k]（k=size()/2），偶数需确保第k-1和k小元素就位，可两次nth_element或partial_sort；注意迭代器安全与原容器修改。

用 nth_element 求中位数最快，但别直接传 begin() + size()/2 就完事

中位数本质是“排好序后下标为 size()/2 的那个数”，nth_element 正是干这事的：它把第 n 小的元素放到位置 n，左边都 ≤ 它、右边都 ≥ 它——不全排序，O(n) 平均复杂度。

常见错误是写成：nth_element(v.begin(), v.begin() + v.size()/2, v.end())，然后直接取 v[v.size()/2]。这在偶数长度时错：中位数应是中间两数平均值，而 nth_element 只保证第 k 位正确，不保证左右子区间有序。

• 奇数长度：取 v[k]（k = v.size()/2）即可
• 偶数长度：需确保第 k-1 和 k 小的数都在正确位置，得调两次或改用 partial_sort
• 如果原容器不能修改，必须先拷贝；nth_element 会重排原数据

nth_element 的迭代器偏移容易算错，尤其用 vector::data() 或指针时

传给 nth_element 的第二个参数是“目标位置的迭代器”，不是下标。有人写 v.data() + v.size()/2，看似对，但若 v 是空容器，v.data() 可能为 nullptr，加法未定义；更安全的是统一用 v.begin() + k，STL 迭代器支持随机访问加法，且空容器时 v.begin() == v.end()，加 0 也合法。

• 安全写法：auto k = v.size() / 2; nth_element(v.begin(), v.begin() + k, v.end());
• 若用 int 下标计算 k，注意 v.size() 是 size_t，大容器时 v.size()/2 不会溢出，但显式转 int 可能截断（如 size > INT_MAX）
• 不要混用 v.data() + k 和 v.begin() + k：前者是裸指针，后者是迭代器；虽多数实现等价，但标准不保证指针可替代迭代器

偶数长度中位数必须处理两个位置，nth_element 本身不保序

nth_element 只保证第 n 位元素就位，左边无序、右边也无序。所以当 v.size() 为偶数时，中位数是第 k-1 小和第 k 小的平均值（k = v.size()/2），但第一次调用只固定了第 k 位，第 k-1 位可能还在左边乱序区里。

立即学习“C++免费学习笔记（深入）”；

• 简单做法：先调 nth_element 把第 k 位放好，再对左半段（v.begin() 到 v.begin() + k）调一次 nth_element 找最大值（即第 k-1 小）
• 更稳做法：用 partial_sort(v.begin(), v.begin() + k + 1, v.end())，它把前 k+1 小的数排好序，然后取 v[k-1] 和 v[k]
• 性能权衡：两次 nth_element 平均 O(2n)，partial_sort 是 O(n log k)，k≈n/2，实际差别不大，但代码更直白

自定义类型或比较逻辑时，nth_element 的第三个参数不能漏

默认按 比较，但遇到 <code>struct、pair 或需要降序时，必须显式传比较函数。漏掉会导致编译失败或逻辑错——比如想求“最大值”当“上中位数”，却忘了用 greater<int>()</int>，结果还是求最小值位置。

• 升序第 k 小：nth_element(a, a+k, b)（默认）
• 降序第 k 小（即第 k 大）：nth_element(a, a+k, b, greater<int>())</int>
• 自定义结构体：nth_element(v.begin(), v.begin()+k, v.end(), [](const auto& x, const auto& y) { return x.val
• 注意：比较函数语义必须是“严格弱序”，返回 true 表示第一个参数应排在第二个之前；反了会导致行为未定义

中位数问题最易被忽略的点是：它依赖数据分布和容器状态。同一份数据，nth_element 后再调一次，结果可能不同——因为算法内部有随机化（部分实现用 introselect，带 pivot 随机选择）。别假设多次调用位置不变。