std::nth_element是找中位数的首选，因其均摊O(n)、内置优化且规避最坏情况；需注意索引计算、容器可修改性及随机访问要求。
为什么 std::nth_element 是找中位数的首选
直接调用 std::nth_element 就能均摊 O(n) 找到中位数，不用手写 partition 循环或递归——它内部就是快速选择（Quickselect）的工业级实现，做了三数取中、小数组切片优化、尾递归消除，还规避了最坏 O(n²) 的常见坑。
常见错误是误用 std::sort 或 std::partial_sort：前者 O(n log n) 过重，后者在找单个中位数时仍做多余排序；还有人手动实现但忘了随机打乱，一遇到已排序数组就退化。
- 对偶数长度数组，中位数定义为第
n/2小（0-indexed），即std::nth_element(v.begin(), v.begin() + v.size()/2, v.end()) - 若需严格按数学定义（偶数时取中间两数平均），先取第
(n-1)/2和n/2小两个位置，再平均——注意两次调用std::nth_element会改变原数组顺序，应只调一次 + 一次扫描比较 - 输入容器必须支持随机访问迭代器（
std::vector、std::array可，std::list不可）
手写快速选择时必须加随机化 pivot
不随机选 pivot 的快速选择，在已排序或逆序数组上必退化成 O(n²)。C++ 标准库实现默认随机，但自己写时容易忽略这一步。
实操建议：用 std::random_device 和 std::mt19937 生成索引，交换到末尾再 partition；不要用 rand()（低质量、非线程安全）。
立即学习“C++免费学习笔记（深入）”；
int quickselect(std::vector<int>& arr, int left, int right, int k) {
if (left == right) return arr[left];
std::random_device rd;
std::mt19937 g(rd());
std::uniform_int_distribution<int> dist(left, right);
std::swap(arr[dist(g)], arr[right]); // 随机换 pivot 到末尾
int pivot_idx = partition(arr, left, right);
if (k == pivot_idx) return arr[k];
else if (k < pivot_idx) return quickselect(arr, left, pivot_idx - 1, k);
else return quickselect(arr, pivot_idx + 1, right, k);
}
std::nth_element 的边界行为和 const 安全性
它不保证“前 k 个元素有序”，只保证第 k 个位置放对了值，且左边 ≤ 它、右边 ≥ 它——这对中位数足够，但别指望它返回一个排好序的半数组。
它会修改原容器，所以传入 const std::vector<int>& 编译失败；若原始数据不可改，必须先拷贝一份（std::vector<int> copy = original;），这点常被忽略导致运行时崩溃或静默错误。
- 当
k超出[0, size)范围，行为未定义（不是抛异常，是 UB）——务必检查k = size/2是否合法（空容器时size()==0） - 对于
float或自定义类型，需确保<可用且满足 strict weak ordering；用std::nth_element(..., std::greater<int>{})可反向找第 k 大 - 在性能敏感场景（如高频调用），避免反复构造 vector 拷贝——可复用 buffer 或用
std::span（C++20）约束视图
中位数计算中容易被绕晕的索引细节
中位数位置取决于“第几小”而非“下标是否居中”。例如 {1,2,3,4}（size=4），数学中位数是 (2+3)/2=2.5，对应第 2 小（index=1）和第 3 小（index=2）；而 size/2 是 2（0-indexed 下标），刚好是后者。但若误用 (size-1)/2 在奇数时又会错位。
统一做法：定义 k1 = (size-1)/2，k2 = size/2（整数除法），两者在奇数时相等，偶数时相邻——这样不用分支判断奇偶。
- 奇数长度：
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end())后取v[v.size()/2] - 偶数长度：必须分别获取
v[(size-1)/2]和v[size/2]，不能只调一次nth_element然后读两个位置——因为 partition 后只有目标位置确定，邻位不保序 - 用
std::vector::data()+std::nth_element可避免迭代器开销，尤其对大数组
实际项目里，95% 的中位数需求用 std::nth_element 加两行索引逻辑就够了；手写快速选择只在需要完全控制 pivot 策略、或嵌入式环境无 STL 时才值得投入。真正难的是把索引算对，而不是算法本身。
