这篇文章我会从 3 个部分讲清楚快速排序：

1. 快速排序到底在做什么
2. 这段代码为什么要这样写
3. 写快速排序时最容易出错的地方有哪些

void quick_sort(int q[], int l, int r)// 快速排序的区间[ l , r )
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
         do i ++ ; while (q[i] < x);
         do j -- ; while (q[j] > x);
         if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

一、什么是快速排序

快速排序的核心思想是：

先选一个基准数 x，再把数组分成两部分：左边都小于等于 x，右边都大于等于 x，然后分别对左右两部分继续进行同样的操作。

这个过程本质上就是一种 分治思想：

• 先解决当前区间的划分问题
• 再递归处理左右两个子区间

举个例子，假设我们有这样一个数组：

6 3 8 2 9 1 5

如果我们选 8 作为基准值，那么一次划分之后，数组会被整理成大致这样的结构：

3 2 1 5 6 | 8 | 9

注意，这里并不要求左半部分和右半部分本身已经有序，只要求：

• 左边的数都不大于基准值
• 右边的数都不小于基准值

接下来再分别对左右两边递归处理，最终整个数组就有序了。

二、快速排序代码

下面是一种非常经典的写法：

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

    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

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

这段代码看起来不长，但里面有不少值得注意的细节。

三、代码逐行解析

1. 递归出口

if (l >= r) return;

当当前区间里只有一个元素，或者没有元素时，就不需要再排了，直接返回。

2. 定义左右指针和基准值

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

这里定义了三个变量：

• i：从左往右找第一个不小于 x 的数
• j：从右往左找第一个不大于 x 的数
• x：基准值，一般取中间位置的元素

其中：

(l + r) >> 1

表示 (l + r) / 2，也就是中间下标。

这里把 i 初始化成 l - 1，把 j 初始化成 r + 1，是为了配合后面的 do...while 写法，让指针移动逻辑更自然。

3. 双指针划分区间

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

这是整个快速排序最核心的部分。

从左往右找

do i++; while (q[i] < x);

这一步会让 i 停在一个“不小于 x”的位置上。

也就是说，q[i] 这个数应该被放到右边去。

从右往左找

do j--; while (q[j] > x);

这一步会让 j 停在一个“不大于 x”的位置上。

也就是说，q[j] 这个数应该被放到左边去。

交换

if (i < j) swap(q[i], q[j]);

如果此时 i 还在 j 的左边，说明这两个位置都找到了“放错边”的元素，那就交换它们。

经过不断交换后，数组就会被分成两部分：

• 左边部分都小于等于 x
• 右边部分都大于等于 x

四、为什么递归是 quick_sort(q, l, j) 和 quick_sort(q, j + 1, r)

很多初学者最容易疑惑的就是这一句：

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

为什么不是 i？

因为循环结束时，j 才是左半部分的最后一个位置。也就是说：

• [l, j] 是左区间
• [j + 1, r] 是右区间

这和当前这份代码的划分方式是配套的，不能随便改。

五、用一个例子理解整个过程

以数组：

4 6 2 8 3 7 1 5

为例，假设当前基准值取中间元素 8。

初始时：

• i 从左边开始找第一个大于等于 8 的数
• j 从右边开始找第一个小于等于 8 的数

很快会发现：

• 左边的 8 应该往右放
• 右边的 5 应该往左放

于是交换。

不断重复这个过程后，数组会被划分成左右两个部分。虽然这两个部分此时还不完全有序，但已经满足“左边小、右边大”的基本结构。接着递归处理左右区间，最终完成排序。

六、快速排序的时间复杂度

快速排序的时间复杂度并不固定。

1. 最优情况

每次都能把数组大致平分：

O(n log n)

2. 最坏情况

每次划分都极不均匀，比如每次只分出一个元素：

O(n^2)

3. 平均情况

平均来说，快速排序的效率通常很好：

O(n log n)

这也是为什么它在实际应用中非常常见。

七、快速排序稳定吗

快速排序是不稳定排序。

所谓稳定，是指如果两个相等的元素原来的相对位置不变，那么这个排序就是稳定的。

而快速排序在交换元素的过程中，可能会打乱相等元素的原有顺序，所以它不稳定。

八、快速排序常见错误

1. 递归边界写错

很多人会把终止条件写错，导致死递归或者数组越界。

正确写法一般是：

if (l >= r) return;

2. 指针初始值写错

如果你使用的是这套模板：

int i = l - 1, j = r + 1;

那后面的扫描方式就应该配套写成：

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

这几部分必须统一。

3. 递归区间写错

这一版代码递归的是：

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

不要随便改成 i，否则很容易出错。

4. 基准值不是下标，而是数值

这里的 x 表示的是：

q[(l + r) >> 1]

也就是中间位置的元素值，不是中间下标。

九、快速排序的优缺点

优点

• 平均效率高
• 思想经典，面试常考
• 原地排序，额外空间较少

缺点

• 最坏情况下会退化到 O(n^2)
• 不稳定排序
• 递归实现对初学者不太直观

十、总结

快速排序的本质可以概括成一句话：

选一个基准值，通过双指针把数组划分成左右两部分，再递归处理左右区间。

真正理解快速排序，关键不是死记代码，而是要明白下面这几点：

1. i 和 j 分别在找什么
2. 为什么交换这两个位置
3. 为什么最后递归的是 [l, j] 和 [j + 1, r]
4. 为什么这是一种分治思想

当你把这几个问题想清楚，快速排序就不难了。