问题描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]
提示：
n == nums.length1 <= n <= 300nums[i]为 0、1 或 2
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
法I：单指针
代码：
//法I：单指针
//两次遍历，常数空间复杂度
//第一次遍历确定0，第二次遍历确定1
class Solution {
public:
void sortColors(vector<int>& nums) {
int head = 0;
//第一遍遍历，找到所有0
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) {
swap(nums[i], nums[head]);
head++;
}
}
//第二遍遍历，找到所有1
for (int i = head; i < nums.size(); i++) {
if (nums[i] == 1) {
swap(nums[i], nums[head]);
head++;
}
}
}
};
执行结果：
分析：
两遍扫描，第一次找到所有的0排在前面，第二次找到所有的1排在0后面，剩下的最后面的就是2了。用head记录头部（第一遍的0或第二遍的1），一个扫描指针i。
法II：双指针（0和2）
代码：
//法II：双指针
//一遍扫描，常数空间
class Solution {
public:
void sortColors(vector<int>& nums) {
int head = 0;
int tail = nums.size() - 1;
int i = head;
while (i <= tail) {
while (i <= tail && nums[i] == 2) {
swap(nums[i], nums[tail]);
tail--;
}
if (nums[i] == 0) {
swap(nums[i], nums[head]);
head++;
}
i++;
}
}
};
执行结果：
第一种方法是两遍扫描，这种方法就是通过一遍扫描来完成了。和第一种方法的思想有一致的地方。这次我们设置的头指针head和尾指针tail来分别记录0和1的位置，同样也有一个扫描指针i来进行一遍扫描。其中head从左向右走，tail从右向左走，扫描指针i也是从左向右扫描。如果nums[i]==0，可以在直接与nums[head]进行交换，之后直接i++，也就是说交换过来的这个元素一定不再是0了（因为i是从左向右扫描的，已经扫描过了）。那么如果nums[i]==2，与nums[tail]交换，之后不能直接i++，因为交换过来的值i还没有扫描过啊，因此我们需要用一个while循环来不断判断交换之后nums[i]是不是2，如果是，就继续交换，一直到nums[i]不是2了才能跳出循环。基于此，我们也可以设置在大的遍历循环中的判断顺序：先判断是否是2，跳出这个判断循环之后再去判断是否是0。（判断顺序很重要！）
法III：双指针（0和1）
这个方法同样是一边扫描。上个方法我们用指向0和2的指针来完成，那么我们用指向0和1的指针来如何完成颜色分类呢？
为了方便理解，这次我们用指针p0指向0，指针p1指向1，两者的初始索引都为0。同样，我们设置一个遍历扫描指针i进行数组的从左向右的扫描。
直接看看代码吧，不想写解释了qaq
代码：
//法III：双指针（0和1）
class Solution {
public:
void sortColors(vector<int>& nums) {
int p0 = 0;
int p1 = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) {
swap(nums[i], nums[p0]);
if (p0 < p1) {
swap(nums[i], nums[p1]);
}
p0++;
p1++;
}
else if (nums[i] == 1) {
swap(nums[i], nums[p1]);
p1++;
}
}
}
};
执行结果：
