【分治】快速排序

912. 排序数组

912. 排序数组

​ 给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

---

解题思路：分治

​ 我们在数据结构阶段学习的快速排序的思想可以知道，快排最核心的一步就是 Partition (分割数据)：将数据按照⼀个标准，分成左右两部分。这种方法的缺点就是遇到大量重复的元素的时候，时间复杂度就相当于是 O(n^2) 了，并且做的都是无效的工作，以至于这道题的官方题解虽然使用的是分为左右两部分的方法，但是依然跑不过去。

​ 而如果我们使用 75. 颜色分类 问题的思想，将数组划分为 左 中 右 三部分：左边是比基准元素小的数据，中间是与基准元素相同的数据，右边是比基准元素大的数据。然后再去递归的排序左边部分和右边部分即可（可以舍去大量的中间重复部分），这 在处理数据量有很多重复的情况下，效率会大大提升。

​ 首先我们得先确定一个能让数组划分的一个基准值，这里采用的是：随机方式选取基准值。这种方式在算法导论中用概率论的知识分析后发现使用该方式选取基准值的话，整个快排的时间复杂度是接近稳定在 O(n * logn) 的，已经是非常高效的了！

​ 其实这并不难，只需要使用接口 rand() 获取随机数，然后模上数组的元素个数即可，但是因为分治的时候研究的是数组中的不同区间，所以还要加上 left 才行，才能让得到的随机数落在以 left 开头的区间，然后返回这个基准值即可！

int random(vector<int>& nums, int left, int right)
{return nums[(rand() % (right - left + 1)) + left];  // 记得要加上left，才能得到落在left以后的区间基准值
}

​ 然后就是之前我们在 75. 颜色分类 学过的划分为三块区间的思想，只不过这里不同的是区间的要求不同罢了！这里就不再赘述了，具体细节可以参考那道题的题解，里面有详细说明，这里直接列出来结论：（下面假设基准值是 partition）

​ 要注意的是，这里的 left 和 right 指针指的依然需要是指定区间的外面，如下图所示：

​ 最后遍历完一遍数组的 [left, right] 区间之后，因为中间的等于 partition 的区间就是固定好的了，相当于就是他们最终在数组中的位置已经找到了，此时 递归去排序左边小于 partition 的部分、右边大于 partition 的部分，直到区间中 left ≥ right 就结束！

class Solution {
public:int random(vector<int>& nums, int left, int right){// 记得要加上left，才能得到落在left以后的区间基准值return nums[(rand() % (right - left + 1)) + left]; }void quicksort(vector<int>& nums, int left, int right){// 终止条件if(left >= right)return;// 获取基准值int partition = random(nums, left, right);int i = left, l = left - 1, r = right + 1; // l和r需要从该区间的左右外边界开始while(i < r){if(nums[i] < partition)swap(nums[++l], nums[i++]);else if(nums[i] == partition)i++;elseswap(nums[--r], nums[i]);}// 递归左右部分，中间部分无需再处理quicksort(nums, left, l);quicksort(nums, r, right);}vector<int> sortArray(vector<int>& nums) {srand((unsigned int)time(nullptr));quicksort(nums, 0, nums.size() - 1);return nums;}
};