给定一个包含红色、白色和蓝色、共 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]提示：
n == nums.length1 <= n <= 300nums[i]为0、1或2
进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
解题思路：分治
所谓分治，无非就是将一个大问题，切分为多个有共同特征的子问题分别去解决，最后子问题解决了，大问题就解决了！最常见的分治思想就是排序算法中的快速排序以及归并排序！
而其中快速排序这个算法在力扣上有个算法题，使用常见的优化快排也是过不了的，所以我们学完分治之后就要看看如何更进一步去优化快排，相当于填了拿那道算法题的坑！
而为了解决那道快排题，我们先来通过这道题学习一下常见的分治思路！这道题其实也借鉴了以前我们在写 283. 移动零 这道题的时候，使用的一个双指针的方法，只不过这道题需要使用三个指针来操作！
首先这道题有一个特征，就是整个数组是可以分为三个部分的，分别是 0、1、2 三个连续数字的板块，所以我们可以想办法用指针来维护它们的边界，于是就想到可以在遍历的时候，将属于哪个板块的数字，就加到哪个板块中，最后遍历完之后就是一个分块的数组！
我们先定义两个指针 left 和 right，分别指向数组的开头的结尾，然后使用 i 来遍历数组，假设数组长度为 n，则此时其实我们可以把数组分为四部分：
[0, left]：全都是0。[left + 1, i - 1]：全都是1。[i, right - 1]：待扫描的区间。[right, n - 1]：全都是2。
根据上面的划分情况，一开始的状态是这样子的：
接着就是不断的移动指针 i，那么 i 遇到的无非就是三种情况：元素为 0、元素为 1、元素为 2。下面我们就来分析一下整个过程：
- 当
nums[i] = 0时：- 因为
[0, left]区间都是0，那么nums[i] = 0的话，我们就要扩大0的区间，就要让nums[left + 1]也变成0，left才能往后移动，但是此时nums[left + 1]位置的元素有两种情况：- 如果
nums[left + 1] = 1的话，那么直接交换nums[left + 1]和nums[i]，并且让left++即可。 - 如果
nums[left + 1] = 0的话，此时只有一种情况，那就是i == left+1，因为nums[left + 1]是0的情况，i肯定是先走过了，left也一定走到了i之前覆盖的所有0的情况了，但是此时nums[left + 1]为0，只能说明它就是一个待扫描的元素，也就是i，此时我们交换nums[left + 1]和nums[i]，其实就相当于i在自己交换自己，所以此时交换完之后不仅要让left++，我们还要让i++才行。
- 如果
- 综上所述，我们要执行的操作就是
swap(nums[++left], nums[i++])，注意这里是先让left向后移动，然后交换完之后再让i向后移动！
- 因为
- 当
nums[i] = 1时：- 这种情况是最简单的，因为
[left, i - 1]区间内都是1，我们只需要让i++即可让当前的1落到新的[left, i - 1]区间内！
- 这种情况是最简单的，因为
- 当
nums[i] = 2时：- 因为
[right - 1, n - 1]区间都是2，所以此时我们要让2的区间扩大的话，就是让right向左移动，那么同样也会遇到和left一样的两种情况，这里就不讨论了，直接给出结论：swap(nums[--right], nums[i])。 - 要注意的是，上面唯一不同的就是交换完之后
i是不需要移动的，因为本身nums[right - 1]就是一个待扫描的元素，所以此时i拿到的就是一个待扫描的元素，所以不需要向后移动，这个要注意！
- 因为
还要注意的是，i 只需要遍历到 right 即可，而不是遍历到 n，因为如果遍历到 n 的话，就会走到全都为 2 的区间，此时就会和 nums[right - 1] 也就是 1 进行交换，顺序就颠倒了！
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int left = -1, right = n, i = 0;
while(i < right) // 注意这里是小于right，不然后面的2部分又会和1部分交换过来
{
if(nums[i] == 0)
swap(nums[++left], nums[i++]);
else if(nums[i] == 1)
i++;
else
swap(nums[--right], nums[i]); // 注意i不需要移动
}
}
};