给定一个包含红色、白色和蓝色，一共 n个元素的数组， 原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 - 你能想出一个仅使用常数空间的一趟扫描算法吗？
基数排序法
可以采用基数排序法的思想，用一个数组记录下 0，1，3 的次数，后重排，这个算法对数组进行了两次遍历。
C++1
class Solution {
public:
void sortColors(vector<int>& nums) {
vector<int> temp(3,0);
for(int i=0;i<nums.size();i++){
temp[nums[i]]+=1;
}
int j=0;
int index=0;
while(j<3){
for(int k=0;k<temp[j];k++){
nums[index++] = j;
}
j++;
}
}
};
一次循环排序的方法
c++2
三路快速排序方法
设置三个 lt, gt, i 定义：nums[0...lt] == 0，nums[lt+1...i-1] = 1，nums[gt...n-1] == 2，遍历一遍改数列保持这个定义。
C++3
class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
int lt=-1, gt=len, i=0;
while(i<gt){
if(nums[i] == 0){
lt++;
int temp = nums[i];
nums[i] = nums[lt];
nums[lt] = temp;
i++;
}
else if(nums[i] == 2){
gt--;
int temp = nums[i];
nums[i] = nums[gt];
nums[gt] = temp;
}
else{
i++;
}
}
}
};
