[数据结构与算法]快速排序法及其优化

快速排序法及其优化

LeetCode：912. 排序数组

思想很简单：先分成两个区，左边比右边都小，然后再对两个区分别进行快排。

分区

分区需要先选一个基准pivot使得左边区的元素都小于pivot，右边元素都大于pivot，这个一般选的是起始元素，但很容易被坑到退化为最差时间复杂度（比如已经排好序的数组，每次都要遍历一整遍数组），这是后话，我们先直接选最左边元素。

注：分区的过程也进行了排序，分区分到最后排序也就排好了。

分区首先得知道左右边界，不然分区都要分到区外了；其次数组肯定得传进来，我们还要改数组，就引用进来；然后分好区总得返回分区结果，我们就返回分区好后的pivot位置，这样左边都小于等于基准，右边都大于基准；如此就得到函数签名应该是这样：

//
/// 快排算法中的分区函数
/// \param l 左边界
/// \param r 右边界
/// \param arr 待排序的数组
/// \return pivot基准值所在的下标
int Partition(int l, int r, vector<int> arr)

现在我们开始实现，直接看比较标准的方法，别瞎想了，下面这段是帮助理解和助记的：

首先pivot已经选定，值已经记录，而且在最左边，比如：

4, 1, 5, 3, 6 // pivot = 4

这时候可以把任何数放在4的位置而不需要tmp存储，因为4已经赋值给pivot了。那么什么是要往4的位置放的呢？自然是小于等于4的元素。这时候你隐约想起来快排的分区函数好像就是先左后右还是先右后左，如果要把小于等于4的元素放到4，自然是先把右边放左边，也就是：右边界的数如果应该在那（> 4）就扔那不管，缩减右边界，一直到右边界的数不该在那了（<=4），我们就停止缩减，然后把那个数放到左边界的位置。之后再反过来，此时右边界的数已经被放到了左边界，相当于做了一次tmp，下一步就是左边界递增，看左边界的数是不是该在那。

从右往左检查
4, 1, 5, 3, 6 // 6 > 4，对的
3, 1, 5, 3, 6 // 3 <= 4，错的！置到左边界

从左往右检查
3, 1, 5, 3, 6 // 3 <= 4，对的
3, 1, 5, 3, 6 // 1 <= 4，对的
3, 1, 5, 5, 6 // 5 > 4，错的！置到右边界

从右往左检查
3, 1, 5, 5, 6 // 5大于4，对的
3, 1, 5, 5, 6 // 左右边界相遇了，相遇的位置即是pivot应该在的位置，即左边都小于pivot，右边都大于它

3, 1, 4, 5, 6 // 最后记得把pivot放回来

都这样了，代码实现就算稍微记一下也得会了吧：

int Partition(int l, int r, vector<int> &arr) {
    int pivot = arr[l];
    while (l < r) {
        while (l < r && arr[r] > pivot) {
            --r;
        }
        arr[l] = arr[r];
        while (l < r && arr[l] <= pivot) {
            ++l;
        }
        arr[r] = arr[l];
    }
    arr[l] = pivot;
    return l;
}

递归快排

已经分了两个区，直接分别快排递归就好：

void QuickSort(int l, int r, vector<int> &arr) {
    if (l >= r) return; // 递归的终止条件
    int idx = Partition(l, r, arr);
    QuickSort(l, idx - 1, arr);
    QuickSort(idx + 1, r, arr);
}

放到一块：

#include <iostream>
#include <vector>

using namespace std;

int Partition(int l, int r, vector<int> &arr) {
    int pivot = arr[l];
    while (l < r) {
        while (l < r && arr[r] > pivot) {
            --r;
        }
        arr[l] = arr[r];
        while (l < r && arr[l] <= pivot) {
            ++l;
        }
        arr[r] = arr[l];
    }
    arr[l] = pivot;
    return l;
}

void QuickSort(int l, int r, vector<int> &arr) {
    if (l >= r) return; // 递归的终止条件
    int idx = Partition(l, r, arr);
    QuickSort(l, idx - 1, arr);
    QuickSort(idx + 1, r, arr);
}

int main() {
    vector<int> nums = {1, 2, 0, 1, 4, 6, 4, 7, 8, 5, 3};
    QuickSort(0, nums.size() - 1, nums);
    cout << nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        cout << ", " << nums[i];
    }
    cout << endl;
    return 0;
}

优化

目前对快排也是比较清晰了，无非是分区+递归快排，主要过程在分区。

如上只选择左边的数作为pivot有一个缺陷，固定的套路会遇到一个固定的最坏情况，即已经排好序的数组，这样每次都得整个遍历一遍。

怎么破解呢？在最开始选pivot的时候也就隐约能想到了，我每次随机选一个不就行了。将以下部分插入到Partition函数最前面即可

srand(time(nullptr));
int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
swap(arr[l], arr[i]);

注：本打算用中新的randomengine，结果发现生成速度上还是rand()快，看来以后算法题需要的话还是得用老rand()。