【算法专题】快速排序

1. 颜色分类

75. 颜色分类 - 力扣（LeetCode）

        依据题意，我们需要把只包含0、1、2的数组划分为三个部分，事实上，在我们前面学习过的【算法专题】双指针算法-CSDN博客中，有一道题叫做移动零，题目要求是把0移动到数组的最后端，于是我们通过两个指针：一个用于遍历数组、另一个用于将数组划分为零区域和非零区域。类似的，我们可以通过三个指针：一个用于遍历、两个用于将数组划分为三部分，即0、1、2。

        接下来我们要考虑的是遍历数组时遇到不同的情况如何处理，我们可以画一个划分过程中的简单示意图：

接下来分析i遍历时会碰到的三种情况：

然后就是将算法原理转化为代码，建议大家可以拿出纸笔，找个例子来模拟一遍，这样能对原理有更深的理解，也有利于接下来代码的编写。

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int i = 0, left = -1, right = n;while(i < right){if(nums[i] == 0) swap(nums[i++], nums[++left]);else if(nums[i] == 1) i++;else swap(nums[i], nums[--right]);}    }
};

2. 排序数组

912. 排序数组 - 力扣（LeetCode）

        这道题目要求我们将给定数组进行升序排列，既然本文标题是快速排序，这里当然是用快排来解决啦！快排的原理是：选择一个基准元素，然后让数组中小于等于基准元素的元素都排在基准元素左侧，大于基准元素的元素都排在基准元素右侧，然后对左侧区间和右侧区间分别做同样的操作，体现了分而治之的思想。

        不过一般的快排可不能解决这道题，因为快排虽然在平均情况下挺高效的，但出现相同元素的个数会影响快排的稳定性。

如上图所示，在最极端的情况下，整个数组都是相同的元素，则每次排序只能确定一个元素的位置，此时快排的时间复杂读退化到了O(n^2)。而本题的用例正好就出现了许多相同元素的情况，所以常规快排是会超出时间限制的，我们需要优化过的快速排序。

        相信大家都发现了，普通快排没有单独考虑相同元素的情况，于是会被相同元素影响到效率，故而我们可以针对这一点进行优化。单独考虑相同元素的情况后，我们将数组划分为三个区域：小于基准元素、等于基准元素、大于基准元素。没错，实际上这里的划分方式和上一道颜色分类是一样一样的。接下来要做的就是确定基准元素，方法有很多，不过算法导论中证明了，随机选取基准元素的快速排序的效率是最高的，因此我们在这里使用随机基准元素。

        

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL)); // 种下随机数的种子，之后我们就可以通过rand()函数得到随机数了qsort(nums, 0, nums.size() - 1);return nums;}// 值得注意的是，本题数据量比较大，我们传数组的引用就不需要进行拷贝了，能大大减少耗时void qsort(vector<int>&nums, int l, int r) {if(l >= r) return;int key = GetRandom(nums, l, r);int i = l, left = l - 1, right = r + 1;while (i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}qsort(nums, l, left);qsort(nums, right, r);}int GetRandom(vector<int>& nums, int left, int right){int index = rand();// 随机数取模区间大小就是偏移量，再加上left，就得到了随机元素的下标return nums[index % (right - left + 1) + left]; }
};