[Lc7_分治-快排] 分治 | 颜色分类

分治

1.颜色分类

题解

2. 快速排序

题解

分治

分治思想就如同它的名字一样：分而治之

将一个大问题划分成若干个相同或者相识的子问题。
然后在将子问题在划分成若干个相同或者相识的子问题，运用递归，直到划分到不能在划分。
然后解决子问题，子问题都解决完了，大问题也就被解决完了。
快速排序和归并排序就用的分治思想。

以前我们学快速排序是在数组中选择一个基准元素，然后将数组分成左右两个区间，左区间比基准元素小，右区间比基准元素大。
然后递归的去左区间和右区间再选择基准值继续排序，这种做法是将数组分成了两份。
但是对于重复元素非常多的数组即使使用快速排序也会超时。

因此这里我们学习新的划分方法，将数组划分成三份。

还是选一个基准元素将数组划分成三份

左区间元素都比基准元素小。
中间区间元素和基准元素相同。
右区间元素都比基准元素大。

因为中间都是等于key的一定就是在最终位置，所以接下来递归还是只考虑左区间和右区间。

1.颜色分类

题目链接：75. 颜色分类

题目分析：

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

题解

说起来这道题并不是真正的分治快速排序，而是把数组按照一定规则划分成三块。

当把这道题解决后，快排写的就非常简单。
这道题就相当于选择一个基准元素1，把小于1的放左边，大于1的放右边，等于1的放中间。
[<1] [=1] [>1]

双指针可以将数组分成两块，具体怎么分，可见双指针系列第一道题移动零（[Lc(1)双指针_1] 移动零 | 复写零 | 快乐数）

这里我们需要三个指针将数组分成三块！

每个指针的作用：

i指针：遍历整个数组
left：标记 0 区域的最右侧
right：标记 2 区域的最左侧

三个指针将数组分成4份：

[0，left] ：全都是0
[left+1，i-1]：全都是1
[i，right-1]：待扫描的元素
[rigth+1，n-1]：全都是2

接下来就讨论nums[i]是0或1或2应该怎么办？

当nums[i]为0的时候，要把0加入到左边区域，left指向的是 0 最右侧区域，此时left+1，然后将 i 位置和 left+1 元素交换，然后i+1。

还有一种极端情况 i 就在 left+1的为位置，并且正好是0。但是这种处理方法和上面一样。
当nums[i]为1的时候，i 指针往后走就行了
当nums[i]为2的时候，我们要将2加入到右边区间，也就是加入到 right - 1 的位置。

交换 i 位置和 right -1 位置的元素。但是此时需要注意的是交换给 i 位置的元素是待扫描的元素，因此 i 指针不能往后走！

class Solution {
public:void sortColors(vector<int>& nums) {//三指针int left=-1,i=0;int n=nums.size(),right=n;
//初始化：left和right 都要初始化在 数组之外while(i<right){if(nums[i]==0)swap(nums[++left],nums[i++]);else if(nums[i]==1)i++;else if(nums[i]==2)swap(nums[--right],nums[i]);}}
};

2. 快速排序

题目链接：912. 排序数组

题目描述：

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

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

示例 2：

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

题解

在数组中选择一个基准元素key
根据key将数组分成左右区间，左区间元素小于等于key，右区间元素大于key。
这个key就处于排序的最终位置。然后在将左区间排排序，右区间排排序

重复上述过程。整体就有序了。时间复杂度(nlogn)

但是如果数组都是重复元素，此时选择基准元素间将数组分成左右两区间就不行了。时间复杂度退化成O(n^2)

所以我们学习一个更优的做法，将 数组分三块 思想来实现快速排序

我们先选一个基准元素key，将数组分成三块。
左区间小于key，中间区间等于key，右区间大于key。
中间区间已经在排序后的最终位置，所以只用去去左区间排序，右区间排序。

重复上述过程，整体就有序了。

数组如何分三块和颜色分类一模一样。

定义一个i 指针扫描数组
left指针指向左区间小于key的最右侧
right指针指向右区间大于key的最左侧。（left 和 right 最开始都要置空）

然后分情况讨论就好了。

即使数组全部都是重复元素，我们经过一次数组划分，整个数组都是中间区间，左右区间不存在，也不用在递归下去了，直接结束。时间复杂度O(n)

优化：用随机的方式选择基准元素

之前常用的三数取中，还是不够随机。

要想时间复杂度逼近O(nlogn) (有 logN 层，每层的划分操作耗时趋近于 N) 就要用随机的方式选择基准元素。
随机选择就是让数组中每个元素被选择的概率相同，然后返回被选择的元素。
通过随机基准元素，以此来避免极端情况，来维持递归树的 logN 层

使用产生随机数的函数 rand()，让生成的随机数%这个区间的长度，然后加上left，

是在这个区间内的随机数的下标，然后返回对应下标的元素。

C++的随机数种子埋法

  srand((unsigned int)time(nullptr));
//后 调用 rand()，即是 随机数了

完整代码：

双指针法

#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;class Solution {
public:vector<int> sortArray(vector<int>& nums) {int n = nums.size();srand((unsigned int)time(nullptr));QuickSort(nums.data(), 0, n-1); // 关键修正1：传递vector的裸指针return nums;}void QuickSort(int* a, int begin, int end) {if(begin >= end) return;int keyi = PartSort(a, begin, end); // 关键修正2：分区逻辑调整QuickSort(a, begin, keyi-1);QuickSort(a, keyi+1, end);}int PartSort(int* a, int left, int right) {int pivot_idx = rand() % (right - left + 1) + left; // 关键修正3：正确随机范围swap(a[pivot_idx], a[left]);int pivot = a[left];// 双指针法分区int i = left, j = right;while (i < j) {while (i < j && a[j] >= pivot) j--; // 从右找小while (i < j && a[i] <= pivot) i++; // 从左找大if (i < j) swap(a[i], a[j]);}swap(a[left], a[i]); // 基准归位return i;}
};

三指针法

class Solution {
public:vector<int> sortArray(vector<int>& nums){int n=nums.size();//种 随机数 种子srand((unsigned int)time(nullptr));QuickSort(nums,0,n-1);//使用 nums.data() 获取vector的裸指针return nums;}void QuickSort(vector<int>& nums,int l,int r){if(l>=r) return;//递归 终止条件//数组分三块int key=nums[rand()%(r-l+1)+l];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++;elseswap(nums[--right],nums[i]);}//递归//通过栈，先进后出，来实现对于 重复性工作 化大为小的计算QuickSort(nums,l,left);//左边界--左指针位置QuickSort(nums,right,r);}
};