快速排序详解

核心思想

快速排序采用分治思想：选择一个基准值，将区间划分为左右两部分，再分别递归处理两个子区间。

算法步骤

在当前区间中选择一个基准值 x。
使用左右指针扫描区间。
将小于 x 的元素放到左侧，大于 x 的元素放到右侧。
递归排序划分后的两个子区间。

为什么需要两个指针？

左指针负责寻找不应该留在左侧的较大元素，右指针负责寻找不应该留在右侧的较小元素。找到后交换二者，直到两个指针相遇。

执行过程

快速排序划分过程

假设基准值为 x：

指针 i 从左向右移动，直到找到大于等于 x 的元素。
指针 j 从右向左移动，直到找到小于等于 x 的元素。
当 i < j 时交换两个元素，继续扫描。
指针相遇后，当前区间划分完成。

完整代码

点击展开 C++ 代码

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;

    int x = q[(l + r) / 2];
    int i = l - 1;
    int j = r + 1;

    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);

        if (i < j) {
            std::swap(q[i], q[j]);
        }
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

关键代码说明

递归终止条件

指针扫描与交换

递归处理子区间

1	if (l >= r) return;

当区间为空或只剩一个元素时，该区间已经有序，直接结束递归。

while (i < j) {
    do i++; while (q[i] < x);
    do j--; while (q[j] > x);
    if (i < j) std::swap(q[i], q[j]);
}

左右指针分别寻找需要交换的元素，交换后继续向中间移动。

1 2	quick_sort(q, l, j); quick_sort(q, j + 1, r);

划分结束后，分别处理左区间和右区间。

复杂度

平均情况

时间复杂度为 O(n log n)，划分较均匀时性能很好。

最坏情况

时间复杂度为 O(n²)，通常发生在划分结果严重不均匀时。

使用建议

实际使用时应避免每次都选择极端位置的元素作为基准值。选择中间元素或随机元素，可以降低出现最坏情况的概率。