【萌新也能看懂的算法入门指南(1)】——快速排序

1. 快速排序快速简介

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序个项目要 $\Theta(nlogn)$ 次比较。在最坏状况下则需要 $\Theta (n^2)$ 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环（inner loop)可以在大部分的架构上很有效率地达成。

2. 快速排序思想

快速排序使用的是分治法中分而治之的思想，把一个待排序的序列分成两个子序列，然后递归的对两个子序列进行操作。（尽量使两个子序列大小接近能获得最优性能）

对某个下标范围为 $[l, r]$ 的序列的操作步骤如下：

Step1：挑选一个基准值：从数列中以某种方法挑出一个元素，称为 “基准”（pivot）;
Step2：划分(partition)：以某种方法将序列重新排序，获得一个新的序列，其满足所有比基准值小的元素都摆放着基准的前面，所有比基准大的元素都摆放在基准值的后面，与基准值相同的元素放到任意一边均可。当划分完成后，基准值所在位置即其最终的位置。
Step3：递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归基: 当序列的长度为 0 或 1 时，此时数组显然已经有序。

3. 排序步骤详解

选取基准值

首先，选取基准值有数种方法，不同的选取方法对整个排序的性能有决定性影响。

一般有以下几种方法：

选取序列最左边或者最右边的元素作为基准值
选取序列中点作为基准值
使用 random 方法来随机选取基准值

其中，如果面对的是所有元素均相同的数组，上述的选取基准值时间复杂度均会退化到 $\Theta(n^2)$ ，需要在划分步骤进行改进，但实际情况很少会遇到这种情况。

另外，第一种方法在面对有序数组时，时间复杂度也会退化到 $\Theta(n^2)$ ，所以，一般使用第 2 种或第 3 种方法最佳。

划分

我们对某个序列进行划分时，一般使用双指针的方法：

令 $l$ 指针(初始指向区间左端点位置）从左向右扫描
令 $r$ 指针(初始指向区间右端点位置)从右向左扫描

首先，让 $r$ 指针先行动，当 $r$ 指针找到比基准值小的元素时，则停止，然后将 $r$ 指针位置上的元素赋值给 $l$ 指针所指位置的元素。

紧接着，让 $l$ 指针行动，当 $l$ 指针找到比基准值大的元素时，则停止，然后将 $l$ 指针位置上的元素赋值给 $r$ 指针所指位置的元素。

重复上述两个步骤，直到不满足 $l < r$ 的条件为止。

最后，将基准值 $pivot$ 赋值给 $l$ 指针对应的位置即可。

举例

初始状态如下图：（选取数组 array 的左端点值作为 pivot)

right指针左移，直到不满足条件 $arr[right] > pivot$ 为止：

将 right 指针对应位置的值赋值给 left 指针对应的位置：

left指针右移，直到不满足条件 $arr[left] <= pivot$ 为止：

注，这里带上等号是为了防止类似以下的这种情况：

[5, 5, 3, 1, 2, 5, 5]，如果不幸选取 pivot = 5, 那么左右指针不会行动，最后出现死循环。

将 left 指针对应位置的值赋值给 right 指针对应的位置：

中间过程同上，直接跳到不满足 $left < right$ 的情况：

当进行到当前步骤时，left 指针右移一步后就就与 right 指针相遇，跳出循环。

将基准值赋值给 left 指针所指位置即可。

这样，基准值 3 的最终位置就确定下来（即下标2），然后，我们递归的对子序列[0, 1]和子序列[3, 6]进行排序即可。

4. 时空复杂度分析

5. 代码实现

以这道 Leetcode： 912. 排序数组为例实现上述整个排序思想：

class Solution {
public:
    static void quick_sort(vector<int>& arr, int l, int r) {
        if(l >= r) return ;
        int index = rand() % (r - l + 1) + l;
        swap(arr[index], arr[l]);
        int pivot = arr[l];
        int i = l, j = r;
        while(i < j) {
            while(i < j && arr[j] >= pivot) j--;
            arr[i] = arr[j];
            while(i < j && arr[i] <= pivot) i++;
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        quick_sort(arr, l, i - 1);
        quick_sort(arr, i + 1, r);
    }
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};

另一种划分的方式：

class Solution {
public:
    static void quick_sort(vector<int>& arr, int l, int r) {
        if(l >= r) return ;
        int pivot = arr[(l + r) >> 1];
        int i = l - 1, j = r + 1;
        while(i < j) {
            while(arr[++i] < pivot);
            while(arr[--j] > pivot);
            if(i < j) swap(arr[i], arr[j]);
        }
        quick_sort(arr, l, j); // 此时因为--j的原因，使得j正好落在左区间右端点上[l, j]
        quick_sort(arr, j + 1, r); [j + 1, r]
    }
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};