中值切分不能直接调用std::nth_element，因其仅保证第k位为中值，不保证左右分区满足≤/＞中值的连续性，尤其重复值时会导致≤部分分散；需先定位中值再用三路划分实现紧凑切分。
中值切分为什么不能直接调用 std::nth_element
因为 std::nth_element 只保证第 k 个位置放好中位数，左右不保证有序，但“中值切分”通常指将数组划分为「≤ 中值」和「＞ 中值」两段（或类似语义），且要求切分后两段连续、可直接用于后续分区（比如快速排序递归、构建平衡BST等）。直接用 std::nth_element 后，若中值重复出现，≤ 部分可能跨在左右两侧，无法得到紧凑的左段。
常见错误现象：std::nth_element(v.begin(), v.begin()+mid, v.end()) 执行后，v[mid] 是中值，但 v[0..mid] 里可能混有 > 中值的元素（尤其当有大量重复值时）。
- 正确做法是：先用
std::nth_element定位中值，再用std::partition或双指针扫描做稳定切分 - 若数组长度为偶数，中值定义需明确：取下中位数（
floor((n-1)/2)）还是上中位数？多数场景用下中位数（即索引n/2对应的元素，C++ 中std::nth_element常用v.begin() + n/2） -
std::nth_element平均 O(n)，最坏 O(n²)；配合std::partition总体仍是 O(n)，但常数略高
用双指针原地切分避免额外内存和迭代器失效
对原始数组（如 std::vector<int>& 或裸指针）做中值切分，最高效的方式是手写三路划分（类似快排 partition），一次遍历完成 ≤ / == / > 三段分离，再根据需求合并 == 段到左侧或右侧。
典型使用场景：实现无栈递归的快速选择、构建线段树的中位数分割点、离散化前的分治预处理。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 关键参数差异：
std::partition只支持二元谓词（如x <= pivot），但无法处理重复中值的归属倾向；手写双指针可控制相等元素全归左边（左闭右开切分） - 性能影响：手写循环比
std::partition少一次函数调用开销，且 CPU cache 更友好；对小数组（n < 64）优势明显 - 示例核心逻辑（假设已知中值
pivot）：
int i = 0, j = 0, k = n;
while (j < k) {
if (arr[j] < pivot) std::swap(arr[i++], arr[j++]);
else if (arr[j] > pivot) std::swap(arr[--k], arr[j]);
else ++j;
}
// 此时 [0, i) ≤ pivot，[i, k) == pivot，[k, n) > pivot
// 若需“≤ 中值”为左段，则切分点为 k（即左段长度 = k）
处理重复中值时的边界陷阱
中值切分最易出错的地方不是算法本身，而是对“中值”的定义与切分目标不一致。例如：std::vector<int> v = {3,3,3,3}，n=4，下中位数索引是 2，v[2]==3，但所有元素都等于中值。此时若强行要求左段长度为 n/2 == 2，必须接受左段只是任意两个 3，而非语义上的“≤ 中值”的自然结果。
- 错误做法：用
std::lower_bound找第一个 > pivot 的位置——它依赖已排序，而输入未排序 - 正确思路：先
std::nth_element得 pivot，再用三路划分确定 - 兼容性注意：C++17 起
std::nth_element对std::vector<T>保证 pivot 值稳定；但若 T 是自定义类型且比较算子不满足严格弱序，行为未定义 - 若需稳定切分（相同值相对顺序不变），只能退化为
std::stable_partition，但时间复杂度升至 O(n log n) 且空间 O(n)
完整可运行的切分函数模板
下面是一个兼顾通用性、安全性和效率的切分函数，返回左段长度（即 ≤ 中值的元素个数）：
template <typename RandomIt, typename Compare = std::less<>>
size_t median_partition(RandomIt first, RandomIt last, Compare comp = {}) {
if (first == last) return 0;
auto n = std::distance(first, last);
auto mid = first + n / 2;
std::nth_element(first, mid, last, comp);
auto pivot = *mid;
// 三路划分：[first, i) < pivot, [i, j) == pivot, [j, last) > pivot
auto i = first, j = first, k = last;
while (j < k) {
if (comp(*j, pivot)) std::iter_swap(i++, j++);
else if (comp(pivot, *j)) std::iter_swap(--k, j);
else ++j;
}
return std::distance(first, k); // 左段包含所有 <= pivot 元素
}
调用方式：size_t left_len = median_partition(v.begin(), v.end());，之后 v[0..left_len) 即为 ≤ 中值部分。
真正难的不是写对这个函数，而是每次调用前确认：你到底要的是“以中值为界的数值切分”，还是“按中位数位置做的等长切分”。前者依赖值，后者依赖索引——这两个概念在重复值存在时根本不同。
