给定一个包含红色、白色和蓝色，一共n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
class Solution {
public:
void sortColors(vector<int>& nums) {
int count[3]={0};
for(int i=0;i<nums.size();i++)
{
assert(nums[i]>=0 && nums[i]<=2);
count[nums[i]]++;
}
int index=0;
for(int i=0;i<count[0];i++)
nums[index++]=0;
for(int i=0;i<count[1];i++)
nums[index++]=1;
for(int i=0;i<count[2];i++)
nums[index++]=2;
}
};
这道题可以使用三路快排（详情可以查阅相关资料）
class Solution {
public:
//时间复杂度O(n)
//空间复杂度O（1）
//只遍历了一遍
void sortColors(vector<int>& nums) {
int zero=-1;//nums[0...zero]==0 -1这是为了设定标记点+1后就从0开始，-1本身没有意义不能设为0因为这样默认了nums[0]为0
int two=nums.size();//nums[two..n-1]==2，同上
for(int i=0;i<two;)
{
if(nums[i]==1)
i++;
else if(nums[i]==2){
two--;
swap(nums[i],nums[two]);}
else//nums[i]==0
{
assert(nums[i]==0);
zero++;
swap(nums[zero],nums[i]);
i++;
}
}
}
};
