17370845950

std::sort 不是手写快排的替代，因其采用 introsort 混合实现且不暴露分区逻辑；手写快排适用于理解本质、调试边界或禁用 STL 场景；partition 函数需确保左右指针不越界，常见错误是 l

为什么 std::sort 不是手写快排的替代参考

标准库的 std::sort 内部通常用 introsort（快排 + 堆排 + 插入排序混合），不是纯快排，且不暴露分区逻辑。想理解快排本质、调试分区边界、或在嵌入式/教学场景禁用 STL 时，必须手写递归分区版本。

partition 函数怎么写才不越界

常见错误是 l 判定后仍让指针多走一步，导致访问 arr[r+1] 或 arr[l-1]。正确做法是双指针在循环内严格约束索引范围，并在交换前二次检查：

int partition(std::vector& arr, int l, int r) {
    int pivot = arr[r];
    int i = l - 1;
    for (int j = l; j < r; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[r]);
    return i + 1;
}

• l 和 r 必须是有效下标，调用前确保 l
• 主循环用 j ，不是 j ，避免拿 arr[r] 和自己比
• 返回的是新 pivot 位置，后续递归区间为 [l, pos-1] 和 [pos+1, r]

递归调用时栈溢出和性能陷阱

最坏情况（已排序数组）下递归深度 O(n)，极易触发栈溢出；同时小数组线性扫描比递归更快。优化必须做两件事：

• 对小规模子数组（如 length ）切换为 std::insertion_sort 或手写插入排序
• 递归前先处理较小区间，再用尾递归优化大区间（即先递归左半边，右半边用 while 循环代替）
• 随机化 pivot：std::swap(arr[r], arr[l + rand() % (r - l + 1)])，避免退化

迭代版快排真的比递归快吗

迭代实现用显式栈模拟递归，能彻底消除栈溢出风险，但实际性能不一定更高——现代 CPU 对递归调用的预测和缓存友好度很好，而手动栈要额外管理 vector 或 array，还可能因内存分配拖慢。除非明确遇到栈深问题，否则优先优化递归版本，而不是盲目转迭代。

真正影响性能的关键是 pivot 选择、小数组阈值、内存局部性（比如用 std::span 避免 vector 迭代器开销），而不是“递归 or 迭代”这个表层选择。