std::partition不能直接用于快排，因其仅保证谓词真值元素在前、假值在后，不返回pivot下标，也不确保pivot位于分界处，无法满足快排递归划分需求。
std::partition 为什么不能直接当快排的 partition 步骤用
因为 std::partition 只保证“满足谓词的元素在前，不满足的在后”，但不保证 pivot 元素落在分界位置，也不保证左右子区间内部有序或可递归划分——而快排的 partition 必须返回 pivot 的最终下标，且该位置是整个数组的稳定切分点。
常见错误是写成：std::partition(v.begin(), v.end(), [&](int x) { return x ，这看似合理，但 <code>pivot 值本身可能重复、不在原位置，且返回的迭代器不对应任何确定的 pivot 下标，后续无法安全递归。
- 它不接受 pivot 值作为参数，只接受一元谓词
- 若数组含重复值，
std::partition不保证相等元素的相对顺序（不稳定），但快排通常不依赖稳定性 - 性能上虽是 O(n)，但缓存局部性不如手写双指针 partition（后者可一次遍历+原地交换）
手写快排 partition 函数该怎么写才安全
标准快排单次划分的核心是：选一个基准（如末尾元素），把小于它的放左边、大于的放右边，最后把它放到中间分界处，并返回该位置。关键在于「原地交换」和「返回确切下标」。
下面是一个典型安全实现：
立即学习“C++免费学习笔记（深入）”；
int partition(std::vector<int>& arr, int left, int right) {
int pivot = arr[right]; // 选右端为 pivot
int i = left - 1; // i 指向小于 pivot 区域的右边界
for (int j = left; j < right; ++j) {
if (arr[j] <= pivot) {
std::swap(arr[++i], arr[j]);
}
}
std::swap(arr[i + 1], arr[right]);
return i + 1;
}- 必须用
int类型返回下标，不能用迭代器——递归调用需要整数索引 - 注意
++i和j的配合，避免越界；循环范围是[left, right)，pivot 单独处理 - 如果要用首元素作 pivot，需先
std::swap(arr[left], arr[right])，否则逻辑错乱
std::partition 在哪些场景下真能替代手写 partition
当你不需要快排语义，只需求“按条件二分数据”且不关心 pivot 位置时，std::partition 简洁可靠。典型如：分离正负数、提取非零元素、预处理过滤边界。
例如将负数放前、非负放后：
std::vector<int> v = {-2, 3, -1, 0, 4};
auto it = std::partition(v.begin(), v.end(), [](int x) { return x < 0; });
// v 变为 {-2, -1, 3, 0, 4}，it 指向第一个非负数（3）
- 返回的是迭代器，不是下标；若需下标，得手动计算
std::distance(v.begin(), it) - 若容器是
std::list，应改用std::list::partition成员函数，避免随机访问开销 - 谓词捕获变量时注意生命周期，比如引用外部 vector 元素可能导致悬垂
std::nth_element 是不是更好的“快排分区”选择
是的——如果你其实只需要“找到第 k 小的元素并完成相应划分”，std::nth_element 比手写 partition 更合适。它内部使用了优化的 introselect 算法，平均 O(n)，最坏 O(n log n)，且保证 [begin, nth) 都 ≤ *nth，(nth, end] 都 ≥ *nth。
例如求中位数或 top-K：
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2};
std::nth_element(v.begin(), v.begin() + 3, v.end()); // 使第 4 小元素就位
// v[3] 现在是 3，且 v[0..3] ≤ 3，v[4..end] ≥ 3（顺序不定）
- 它不排序整个区间，比
std::sort快，也比反复调用手写 partition 稳定 - 不可用于实现完整快排，因为它不保证左右子区间可继续独立 nth_element
- 注意第三个参数是
v.end()，不是v.begin() + v.size()——虽等价，但前者更惯用且防溢出
实际用 std::partition 时，多数人想的是“快排那一下”，结果掉进语义陷阱；真正要快排，就老老实实写 partition 或用 std::nth_element；要简单二分数据，才轮到 std::partition 上场。pivot 位置是否可控，是区分它们的硬边界。
