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