//问题：颜色排序（以后看可不可以用partition）
//双指针法，只能用于只有三类的排序，不过只需一次遍历
#include <algorithm>
class Solution
{
public:
void sortColors(vector<int>& A)
{
int left=0,right=A.size()-1;//双指针，left从左边扫描，right从右边扫描
for(int i= 0;i<=right;i++) //扫描到right即可
{
if(A[i] == 0) swap(A[i++],A[left++]); //将0换到左边
else if(A[i] == 2) swap(A[i--],A[right--]); //将2换到右边，i--是以免right换过来的值为0（抵消for循环中的i++）
}
}
};
//存储后移法（相当于直接插入排序,只不过预先知道了有哪些数，故简单一点）
class Solution
{
public:
void sortColors(vector<int>& A)
{
int n0,n1,n2;//类别索引
n0 = n1 = n2 = 0;
for(int i = 0; i<A.size(); i++)
{
switch(A[i])
{
case 0:
A[n2++] = 2; A[n1++] = 1; A[n0++] = 0;//后面的元素往后移
break;
case 1:
A[n2++] = 2; A[n1++] = 1;
break;
case 2:
A[n2++] = 2;
}
}
}
};
//计数排序，需要两次遍历
class Solution
{
public:
void sortColors(vector<int>& nums)
{
int count[3] = {0};//用于统计每个颜色出现的次数
for(int i=0;i<nums.size();i++) //统计直方图
count[nums[i]]++;
for(int i = 0,index = 0;i<3;i++) //排序
for(int j = 0; j<count[i];j++)
nums[index++] = i;
}
};
