这道题的题意是，给出一个一维数组，数组中的元素只可能是0，1，2，分别表示红色、白色和蓝色。 我们需要做一个排序，使得0全部在数组前面，1在中间，2在后面。 （不过不能用sort函数）

方法一（常数空间，非一趟扫描）

可以用三个变量分别记录红色、白色和蓝色的出现次数，然后根据出现的次数，修改数组即可。

class Solution { public: void sortColors(vector<int>& nums) { vector<int> colorNum(3); //分别记录红色、白色、蓝色出现的次数 for(auto num : nums) { if(num == 0) { ++colorNum[0]; } else if(num == 1) { ++colorNum[1]; } else { ++colorNum[2]; } } for(int i = 0; i < colorNum[0]; ++i) { //把红色放到数组的前面 nums[i] = 0; } for(int i = 0; i < colorNum[1]; ++i) { //白色放中间 nums[colorNum[0] + i] = 1; } for(int i = 0; i < colorNum[2]; ++i) { //蓝色放最后 nums[colorNum[0] + colorNum[1] + i] = 2; } } };

方法二（常数空间，一趟扫描）

由于每一步不是++i就是–k,所以最终i和k总会相遇，这样只需要常数空间，一遍扫描就对数组排好序了。

代码如下:

class Solution { public: void sortColors(vector<int>& nums) { int i = 0, j = 0, k = nums.size() - 1; while(i <= k) { if(nums[i] == 0) { swap(nums[i], nums[j]); //“0的地盘”扩大了，继续判断下一个位置 ++j; ++i; } else if(nums[i] == 1) { //“1的地盘”扩大了，继续判断下一个位置 ++i; } else if(nums[i] == 2) { swap(nums[i], nums[k]); //“2的地盘”扩大了 --k; //注意这里没有++i，对于从位置k交换过来的元素，还是要进行判断滴～ } } } };