std::partition不适合快排原地分区，因其不保证pivot位置可控且不返回pivot下标，无法确定子区间边界；它适用于无序分组而非排序所需的轴心定位。
为什么 std::partition 不适合直接做快排的原地分区
快排原地分区的核心是“单边扫描 + 交换”，而 std::partition 默认按谓词分组，不保证 pivot 位置可控，也不返回 pivot 的最终下标——这意味着你无法知道左右子区间边界，没法递归切分。它更适合“把偶数放前、奇数放后”这类无序分组，而非排序所需的确定性轴心定位。
实操建议：
- 手写分区函数时，固定选
arr[left]或随机索引为 pivot，用i（左边界）和j（右边界）双向收缩 - 避免用
std::nth_element替代——它只保证第 k 位有序，不提供完整分区结构 - 若必须复用 STL，可用
std::partition_point配合自定义比较器，但需提前将 pivot 拷贝出来并重写比较逻辑，反而更重
三路快排（Dutch National Flag）怎么解决重复元素性能崩塌
当数组含大量重复值（如全 5），经典双路快排会退化成 O(n²)，因为每次分区后只排除一个 pivot，其余全挤在一边。三路分区把数组切成 [ pivot] 三段，等于 pivot 的部分直接跳过递归。
关键实现点：
立即学习“C++免费学习笔记（深入）”；
- 维护三个指针：
lt（小于区右界）、gt（大于区左界）、i（当前扫描位） - 遇到
arr[i] == pivot时只i++，不交换；小于则与arr[++lt]交换；大于则与arr[--gt]交换 - 递归只处理
[left, lt]和[gt, right]，跳过中间等值段
示例片段（简化）：
while (i <= gt) {
if (arr[i] < pivot) swap(arr[i++], arr[++lt]);
else if (arr[i] > pivot) swap(arr[i], arr[--gt]);
else i++;
}
如何安全地引入随机化又不拖慢小数组
固定取首/尾元素作 pivot 在有序或近似有序输入下必然触发最坏复杂度。但每次调用 rand() 或 std::random_device 初始化生成器，对小数组（比如 n
折中方案：
- 对长度 ≤ 10 的子数组，改用插入排序——它在小数据上常数低，且稳定
- 对大数组，在
[left, right]内取 3 个随机位置（如left、mid、right），用中位数作 pivot，避免调用真随机数生成器 - 不要在递归每层都 new 一个
std::mt19937——全局静态复用一个即可，注意线程安全
迭代版快排怎么避免栈溢出又保持原地性
递归快排最深可能 O(n) 栈空间（退化情况），而迭代版用显式栈模拟递归，但若不控制入栈顺序，仍可能压入大量待处理区间。关键在“先压大区间、后压小区间”，确保栈深度始终 ≤ log₂n。
操作要点：
- 用
std::stack<pair>></pair>存储[l, r]区间，每次 pop 后做分区，得到lt和gt - 比较两个子区间长度，先把较长的区间 push 进栈，再 push 较短的——这样栈里最多存 log₂n 个区间
- 分区函数仍必须原地完成，不能额外分配内存；所有交换都在原始
vector或裸数组上进行
真正容易被忽略的是：迭代版本丢失了函数调用栈的自然作用域，所有临时变量（如 pivot、指针）必须显式管理，稍不注意就会用错下标或覆盖 pivot 值。
