75. 颜色分类（荷兰国旗问题）
题目
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
荷兰国旗包含三种颜色：红、白、蓝。
有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。它其实是三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。
- 进阶：
你能想出一个仅使用常数空间的一趟扫描算法吗？
解题思路
非进阶思路：
这题我们可以考虑对数组进行两次遍历(使用单指针)。在第一次遍历中，我们将数组中所有的 00 交换到数组的头部（用一个指针pointer来指出头部的范围）。
在第二次遍历中，我们将数组中所有的 11 交换到头部的 00 之后。此时，所有的 22 都出现在数组的尾部，这样我们就完成了排序。
进阶思路：
用双指针
- 两个指针分别指向 下一个0、2应该存放的位置
- 遇0则交换 当前元素 和 p0空间的值，并 使得 p0指针 指向 下一个0应该存放的位置，遍历下一个元素
- 遇2则交换 当前元素 和 p2空间的值，并 使得 p2指针 指向 下一个2应该存放的位置，遍历下一个元素
或者直接快排
代码
非进阶：
class Solution {
public void sortColors(int[] nums) {
int length=nums.length;
int pointer=0;//头部的范围
for (int i = 0; i < length; i++) {
if (nums[i]==0){
int temp=nums[pointer];
nums[pointer]=nums[i];
nums[i]=temp;
//要注意放入最后一个0了 pointer仍然会加一，所以pointer-1，才是真正的头部范围。
pointer++;//将一个元素放到头部后就要给头部范围加1。
}
}
for (int i = pointer; i < length; i++) {
if (nums[i] == 1) {
int temp=nums[pointer];
nums[pointer]=nums[i];
nums[i]=temp;
pointer++;
}
}
}
}
进阶：
class Solution {
public void sortColors(int[] nums) {
/**
* 双指针
* 两个指针分别指向 下一个0、2应该存放的位置
* 遇0则交换 当前元素 和 p0空间的值，并 使得 p0指针 指向 下一个0应该存放的位置，遍历下一个元素
* 遇2则交换 当前元素 和 p2空间的值，并 使得 p2指针 指向 下一个2应该存放的位置，继续遍历 交换后的当前元素
*/
int length=nums.length;
int p0=0;
int p2=length-1;
for (int i=0;i<=p2;i++){//没和p2相遇之前继续循环
if (nums[i]==0){
int temp=nums[p0];
nums[p0]=nums[i];
nums[i]=temp;
p0++;
}
}
for (int i=length-1;i>=p0;i--){//没和p0相遇之前继续循环
if (nums[i]==2){
int temp=nums[p2];
nums[p2]=nums[i];
nums[i]=temp;
p2--;
}
}
}
}
快排版本
class Solution {
public void sortColors(int[] nums) {
quickSort(nums,0,nums.length-1);
}
public void quickSort(int[] nums,int low,int high){
if(low>high){
return;
}
int i=low;
int j=high;
//基准
int temp=nums[low];
while(i<j){
while(temp<=nums[j]&&i<j){
j--;
}
while(temp>=nums[i]&&i<j){
i++;
}
if(i<j){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
//到这里i,j已经重合了
nums[low]=nums[i];
nums[i]=temp;
quickSort(nums,low,j-1);
quickSort(nums,j+1,high);
}
}
