快速排序

1 背景

我们都知道，算法是解决实际问题的步骤，是前人智慧的结晶。那么为什么会有快速排序呢？这就需要了解下传统排序算法的缺点。传统的排序算法有冒泡排序、选择排序和插入排序。它们的共同点就是两两比较，算法的时间复杂度高达 O(n^2)，不适合大规模排序。我们接下来来看下时间复杂度仅为 O(nlogn) 的快速排序算法，它用到了分治思想，非常巧妙。

2 核心思想

分治，顾名思义，就是分而治之，将一个大的问题分解成 n 个规模较小，且结构与原问题相似的子问题，递归地解决这些子问题后，然后再合并其结果，就得到原问题的解。有的同学可能会发现这跟递归的定义有点像，是的，分治算法一般是用递归来实现的。分治是一种处理问题的思想，递归是一种编程技巧，两者并不冲突。

快速排序的步骤：

1. 在数组中选定 pivot（分区点）
2. 将小于 pivot 的数字移到 pivot 的左边
3. 将大于 pivot 的数字移到 pivot 的右边
4. 分别对左右子序列重复前面 3 步

3 案例

接下来我们通过一个例子来一起看下快速排序的过程。

假设有 5 个数字：3, 1, 5, 2, 4。

让我们选一个数字作为 pivot，有多种选择 pivot 的方式，最简单的方式选择第 1 个数字作为 pivot，即选取 3 作为 pivot，并记住它的位置，这个位置就相当于是一个坑：

, 1, 5, 2, 4

设置左右两个指针分别指向数组的最左和最右两个元素：

, 1, 5, 2, 4

￪ ￪

先从右边的指针开始，把右指针指向的元素与 pivot 进行比较。如果右指针指向的元素 >= pivot，则把右边的指针向左移动：

, 1, 5, 2, 4

￪ ￪

如果右指针指向的元素 < pivot，则将右指针指向的元素 2 填入坑中：

2, 1, 5, , 4

￪ ￪

这个时候，2 之前所在的位置成为了新的坑。同时，左指针向右移动一位：

2, 1, 5, , 4

 ￪       ￪

此时，左指针左边的区域代表小于 pivot 的区域。

接下来将左指针指向的元素与 pivot 进行比较。如果左指针指向的元素 <= pivot，则左指针向右移动：

2, 1, 5, , 4

     ￪   ￪

如果左指针指向的元素 > pivot，则左指针指向的元素填入坑中：

2, 1, , 5, 4

     ￪   ￪

这时候 5 之前所在的位置成为了新的坑，同时右指针向左移动一位：

2, 1, , 5, 4

    ￪￪

此时，右指针右边的区域代表大于 pivot 的区域。

当左右指针重合时，可以把 pivot 也就是 3 放到指针重合的位置上：

2, 1, 3, 5, 4

    ￪￪

此时，指针左边的元素都小于 3，右边的元素都大于 3，这一轮交换就结束了。

现在数列被 pivot 划分成了两个未排序的子序列，分别对两个子序列重复前面的步骤即可。

这就是分治的思想，数列每一轮被拆分成两部分，每一部分在下一轮又分别拆分成两部分，直到不可再分为止。

4 代码实现

递归公式：quick_sort(left, right) = quick_sort(left, mid-1) + quick_sort(mid+1, right)

终止条件：left >= right

void quick_sort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = partion(a, left, right);
    quick_sort(a, left, mid - 1);
    quick_sort(a, mid + 1, right);
}

// 将小于 pivot 的元素移到左边，将大于 pivot 的元素移到右边
int partion(int a[], int left, int right) {    
    int pivot = a[left];

    while(left < right) {
        while(left < right && a[right] >= pivot) {
            right--;
        }
        a[left] = a[right];
        while(left < right && a[left] <= pivot) {
            left++;
        }
        a[right] = a[left];
    }
    a[left] = pivot;
    return left;
}

5 性能分析

（时间关系，这部分跳过）

因为划分过程涉及交换操作，如果数组中有两个相同的元素，它们的相对先后顺序可能会改变。所以，快速排序不是一个稳定排序算法。

5.1 时间复杂度

最好情况

划分后，左子序列和右子序列的长度相同，时间复杂度为 O(logn)，递推公式如下：

T(1) = C;  n = 1 时，只需要常量级的执行
T(n) = 2 * T(n/2) + n;  n>1

递归公式的求解比较复杂，我们也可以根据递归树来求解。

最坏情况

序列本身是有序的，划分后的两个序列分别包含 0 个元素和 n-1 个元素，时间复杂度为 O(n^2)，递推公式如下：

T(1) = C;  n = 1 时，只需要常量级的执行
T(n) = T(n-1) + n;  n>1

有点像冒泡排序，每趟排序后只能增加一个元素的有序性。

举个例子，比如 1, 2, 3, 4, 5，如果每次选择第 1 个元素作为 pivot，那么每次分区得到的两个区间都是不均等的。需要进行大约 n 次分区操作才能完成快排的整个过程，每次分区我们平均要扫描大约 n/2 个元素，从而使得时间复杂度退化成了 O(n^2)。

平均时间复杂度

假设每次分区操作都将区间分成 9:1 的两个小区间，时间复杂度为 O(nlogn)，递归公式变成如下：

T(1) = C;   n = 1 时，只需要常量级的执行
T(n) = T(n/10) + T(9*n/10) + n;  n>1

可见，T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下才会退化到 O(n^2)，所以平均时间复杂度也是 O(nlogn)。

5.2 空间复杂度

主要是递归造成的栈空间的使用。

最好情况

递归树深度为 logn，每次递归中只使用了常数的空间，空间复杂为 O(logn)。

最坏情况

需要进行 n-1 次递归，每次递归中只使用了常数的空间，空间复杂度为 O(n)

平均空间复杂度

O(logn)