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 随机选择）。别假设多次调用位置不变。
