题目描述

给定一个带有红色，白色或蓝色的n个对象的数组，对它们进行排序，使相同颜色的对象相邻，颜色顺序为红色，白色和蓝色。

在这里，我们将使用整数0,1和2分别表示红色，白色和蓝色。

注意：
对于这个问题，不应该使用库的排序功能。

样例

输入[1,2,0,1],输出[0,1,1,2]

算法1

(双指针法) 时间$O(n)$ 空间$O(1)$

1. 设置两个index，一个代表0和1的分界线，一个代表1和2的分界线，初始时分别在两边
2. 扫描一遍数组，遇到0则swap后修改0和1的分界线，遇到1则接着遍历，遇到2则swap后修改1和2的分界线

C++ 代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red = 0, blue = nums.size()-1; 
        for(int i=0;i<=blue;){ //注意结束for的条件
            if(nums[i] == 0)    swap(nums[i++],nums[red++]);           
            else if(nums[i] == 2)   swap(nums[i],nums[blue--]);
            else    ++i;

        }
    }
};

算法2

(计数排序法) 时间$O(n)$ 空间$O(1)$

1. 第一次扫描，记录分别有多少个0,1,2
2. 第二次扫描，overwrite数组

C++ 代码

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, t = 0;i < 3; ++i)
            for(int j = 0; j < count[i]; ++j)
                nums[t++] = i;

    }
};

算法3

(快排) 时间$O(n)$ 空间$O(1)$

利用快排中partition的思想。
1. 将数组按0进行切割
2. 将数组中第一步切割后的非0的部分按1进行切割

C++ 代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        partition(
            partition(nums.begin(),nums.end(),bind1st(equal_to<int>(),0)), nums.end(), bind1st(equal_to<int>(),1));
    }
};