[算法]快速排序从入门到被门槛绊倒

一、简介

本文介绍了快速排序的基本思路，并且给出我个人的对快排的记忆方式，方便大家基于该算法快速实现快排。
代码实现以Leetcode-912.排序数组题中的题目代码为模板，可以将自己写的快排代码在该题目中测试代码是否正确。

二、快速排序

1. 基本思想

在基于递归的快速排序算法中，为了对 nums[begin, end] 进行排序，需要进行以下两个步骤：
步骤一：

• 假如 begin==end，即 nums[begin, end] 中只有一个元素，那么就不用排序。
• 否则，在 nums[begin,end]中选择一个元素作为 pivot，然后将 nums[begin,end] 中小于 pivot 的元素放到 nums 的前部分，等于 pivot 的元素放到nums的中间部分，大于 pivot 的元素放到 nums 后部分。如下图所示：

假设 nums[begin,end] 中有 $n_{le}$ 个元素小于等于pivot，有 $n_{eq}$ 个元素等于 pivot,有$n_{gt}$个元素大于 pivot 。
那么经过该步骤一之后，nums 的前部分的元素 $nums[begin,begin+n_{le}-1]$ 的元素都小于pivot（但是$nums[begin,begin+n_{le}-1]$中的元素不一定有序）。$nums[begin+n_{gt},end]$ 中的元素都大于 pivot（但是也不一定有序）。

步骤二：
然后，分别对 $nums[begin,begin+n_{le}-1]$ 和 $nums[begin+n_{gt},end]$使用步骤一进行排序。

2. 基于递归的实现-未优化

一个基于快排思想的初始化代码如下。
步骤一：

• 选择nums中的一个元素设为 pivot（本文中令nums[begin]为pivot），令n=end-begin+1，n即当次排序中的元素个数。申请一个大小等于 n 的 临时数组 temp_nums[0,n-1]；
• 然后遍历 nums[begin, end]，循环变量为 i。
  将 nums[begin,end] 中小于 pivot 的元素依次放入 temp_nums[0]、temp_nums[1]、… temp_nums[$n_{le}$]中；
  将nums[begin, end]中等于 pivot 的元素，忽略不管，直接令 i ++；
  将nums[begin,end] 中大于 pivot 中的元素依次放入 temp_nums[n-1]、temp_nums[n-2]、… temp_nums[$n-n_{gt}$]中；
• 将 temp_nums[$n_{le}$, n-$n_{gt}$-1] 中的元素全部赋值为 pivot；
• 将 temp_nums[0,n-1] 复制到 nums[begin, end]中。
  经过步骤一后，nums[begin, begin+$n_{le}-1$] 中的元素都小于 pivot，nums[begin+$n_{le}$, begin+$n_{g}t$] 中的元素都等于 pivot，nums[end-$n_{gt}+1$, end] 中的元素都大于 pivot。

步骤二：

• 直接对nums[begin, begin+$n_{le}-1$]和nums[end-$n_{gt}$+1, end]执行步骤一即可；

代码如下所示（但是以下代码会因为超出内存限制导致并不能通过Leetcode-912.排序数组）：

class Solution {
public:
    void sort(vector<int>& nums, int begin, int end){
        if(begin>=end){
            return ;
        }
        // 步骤一
        int pivot = nums[begin];
        int n = end - begin + 1;
        
        vector<int> temp_nums(n, pivot);
        int n_le = 0;
        int n_gt = 0;
        for(int i=begin; i<=end;){
            if(nums[i]<pivot){ // nums[i] < pivot
                temp_nums[n_le] = nums[i];
                n_le ++;
                i ++;
            }else if(nums[i]==pivot){ // nums[i] == pivot
                i ++;
            }else{ // nums[i] > pivot
                temp_nums[n-n_gt-1] = nums[i];
                n_gt ++;
                i ++;
			}
        }
        
        copy(temp_nums.begin(), temp_nums.begin()+n, nums.begin()+begin);

        sort(nums, begin, begin+n_le-1);
        sort(nums, end-n_gt+1, end);
    }
    vector<int> sortArray(vector<int>& nums) {
        sort(nums, 0, nums.size()-1);
        return nums;
    }
};

以上代码可以实现 快速排序，但是需要申请一个临时的空间 temp_nums，其实这部分空间可以使用 nums 代替，即在 nums 上原地执行步骤一。

3. 基于递归的实现-优化空间复杂度

一个避免使用 temp_nums 的思想是在遍历 nums 时，我们可以把根据与 pivot 的相对大小，将 nums[i] 重新放在 nums 数组中的不同位置上。具体过程如下：

步骤一：

• 令 left=begin，right=end。我们从 nums[begin] 遍历到 nums[right]（从前往后遍历nums，i 依次从begin到right）。
  假如元素 nums[i]<pivot，那么可以将nums[i] 放入nums[left]，然后令 left++。因为我们是从左往右遍历，那么可以保证 i >= left；
  假如元素 nums[i]==pivot，那么我们不用管它（因为最后我们会把小于pivot和大于pivot的中间部分填充进 pivot）；
  假如元素 nums[i]>pivot，那么我们就将nums[i]放入 nums[right]，然后令 right–。但是这是有问题的，因为 此时我们还没有遍历到 nums[right]，那么此时将 nums[i] 放到 nums[right] 中会覆盖原本的 nums[right] 这个值。因此正确的做法是，交换 nums[i] 和 nums[right]（swap(nums[i], nums[right])）。那么交换完成后， nums[right] 中存的就是 原来的nums[i]（达到了将nums[i]放入到 nums[right]的目的），同时还将原来nums[right]中的值保存了下来。然后判断swap()操作后的 nums[i]（即原来的nums[right]）是小于、等于还是大于 pivot。另外，此时由于nums[right]中的值是已经访问过的值，那么整个遍历流程中 不应该再次遍历该变量，因此需要将循环的终止变量设置为 right（代码中的 for(int i=begin; i<right;)），而不是 for(int i=begin; i<=end;)。

• 之后，我们还是需要将 nums[left, right] 中填入 pivot。
  遍历完 nums[begin, end] 后，nums[begin, left-1]中的元素都小于 pivot，nums[left, right] 中的元素等于 pivot，nums[right+1, end]中的元素是都大于 pivot。

步骤二：
接下来我们只需要对 nums[begin, left-1] 和 nums[right+1, end] 递归的执行步骤一中的操作即可。
完整的代码如下（该部分代码可以顺利的通过Leetcode-912.排序数组）：

class Solution {
public:
    void sort(vector<int>& nums, int begin, int end){
        if(begin>=end){
            return ;
        }
        // 步骤一
        int pivot = nums[begin];
        int n = end - begin + 1;
        int left = begin;
        int right = end;
        for(int i=begin; i<=right;){
            if(nums[i]<pivot){ // nums[i] < pivot
                nums[left] = nums[i];
                left ++;
                i ++;
            }else if(nums[i]==pivot){ // nums[i] == pivot
                i ++;
            }else{ // nums[i] > pivot
                swap(nums[i], nums[right]);
                right --;
            }
        }
        
        fill(nums.begin()+left, nums.begin()+right+1, pivot);
        // 步骤二
        sort(nums, begin, left-1);
        sort(nums, right+1, end);
    }
    vector<int> sortArray(vector<int>& nums) {
        sort(nums, 0, nums.size()-1);
        return nums;
    }
};

4. 基于循环的快排

我们可以使用 栈 来模拟递归实现的快排。
快排部分的整体思路与前面类似，但是不同的是我们使用 栈 手动模拟递归的实现。一个示例代码如下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        stack<pair<int, int>> sta;
        sta.push({0, nums.size()-1});
        while(sta.empty()==false){
            int begin = sta.top().first;
            int end = sta.top().second;
            sta.pop();
            // 步骤一
            if(begin>=end){
                continue;
            }
            int pivot = nums[begin];
            int left = begin;
            int right = end;
            for(int i=begin; i<=right;){
                if(nums[i]<pivot){
                    nums[left] = nums[i];
                    left ++;
                    i ++;
                }else if(nums[i]==pivot){
                    i ++;
                }else{
                    swap(nums[i], nums[right]);
                    right --;
                }
            }
            fill(nums.begin()+left, nums.begin()+right+1, pivot);
            // 步骤二
            sta.push({begin, left-1});
            sta.push({right+1, end});
        }
        return nums;
    }
};