std::sort 绝大多数情况下比手写快排更快更安全，因其采用 introsort（快排+堆排+插入排序混合），避免最坏 o(n²)，自动优化小数组和递归深度；仅在特定场景下手写快排可能占优。
std::sort 是不是比手写快排更快
绝大多数情况下，std::sort 不仅更安全，而且实际运行更快。它在 libstdc++ 和 libc++ 中都不是纯快排，而是 introsort（快排 + 堆排 + 插入排序混合），能避免最坏 O(n²) 情况，同时对小数组自动切到插入排序，对深度递归自动切换为堆排。
手写快排只有在极特殊场景下才可能赢：比如你完全掌控数据分布（如大量重复元素）、内存严格受限、或需要定制分区逻辑（如按多个字段稳定比较）。否则，直接用 std::sort 是更优解。
常见错误现象：std::sort 报错 “invalid comparator”，通常是因为自定义比较函数不满足严格弱序——比如 a 和 <code>b 同时为 true，或 <code>comp(a, a) 返回 true。
- 确保比较函数满足：对任意
a，comp(a, a)必须为 false - 若需稳定排序，改用
std::stable_sort，但注意它平均复杂度仍是 O(n log n)，且常数更大 - 对
std::vector排序，别传&v[0]和&v[0] + v.size()—— 直接用v.begin()/v.end()更安全、可读性更好
手写快排时 pivot 选错会卡成 O(n²)
选第一个/最后一个元素当 pivot，在已排序或逆序数组上会退化。这不是理论风险，是真实高频踩坑点——比如读配置文件后对 ID 列表排序，结果发现某次上线后 CPU 突增。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 用三数取中法：取首、中、尾三个位置的值，选中位数作为 pivot；
std::nth_element可辅助实现，但别在每层递归都调，开销大 - 随机化更简单：在分区前，用
std::uniform_int_distribution随机选一个索引，和首元素 swap - 别用
rand() % size—— 低比特周期短，且rand()在多线程下非线程安全；优先用std::random_device+std::mt19937
原地分区写错导致越界或死循环
经典双指针分区（Lomuto 或 Hoare）里，边界条件稍有不慎就会访问 arr[-1] 或陷入 i 永真循环。尤其在处理重复元素多的数组时，Hoare 版本若不严格控制移动逻辑，很容易漏交换或越界。
推荐用 Lomuto 分区（更易验证），关键点：
- 让
i指向「已处理区」末尾（即所有的右边界），初始为 <code>low - 1 - 遍历
j从low到high - 1，不是high；最后 swaparr[i + 1]和arr[high] - 递归调用时，左右区间分别是
[low, i]和[i + 2, high]—— 注意不是i+1，因为i+1是 pivot 最终位置，已确定
示例片段（简化版）：
void quicksort(vector<int>& arr, int low, int high) {
if (low >= high) return;
int pi = partition(arr, low, high); // 返回 pivot 最终索引
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}迭代版快排为什么比递归版难写还未必更快
用栈模拟递归，本意是防栈溢出，但实际中除非你明确知道输入规模会达到万级深度（比如链表转数组后排序），否则收益有限。现代系统默认栈空间几 MB，对应约 10⁴ 层递归，而快排平均深度仅 O(log n) —— 即使 10⁷ 元素，平均也才约 24 层。
真正容易被忽略的点：
- 手动管理栈时，压入区间顺序影响缓存局部性：先压大区间再压小区间，能降低栈最大深度；但若先压小区间，虽栈深略增，却可能提升 cache hit 率
- 迭代版代码体积翻倍，调试困难，且容易在边界计算（如
left/right开闭区间混用）上出错 - 编译器对尾递归优化有限，但对
std::sort这类高度优化的实现，其内建迭代逻辑已足够健壮——你手写的迭代版几乎不可能超越
除非你在嵌入式环境跑超大数组且禁用栈扩容，否则别碰迭代快排。把精力放在用好 std::sort 和理解它的 fallback 行为上更实在。
