由于使用整数0 1 2分别代表红色 白色 和蓝色，而且是按照红色 白色和蓝色顺序排列。
所以直接排序肯定是正确的。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums.begin(),nums.end());
    }
};

运行效率:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sort Colors.
Memory Usage: 8.3 MB, less than 64.12% of C++ online submissions for Sort Colors.

尝试使用双指针解法,左指针从前往后，又指针从后往前，发现WA，失败的案例2，0，1，原因是想的太简单了，右侧遇到不等2的有可能是1，不能将1放在前面。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0,r = nums.size() - 1;
        while(l < r)
        {
            while(l < r && nums[l] != 2)
                l++;
            while(r > l && nums[r] == 2)
                r--;
            
            swap(nums[l++],nums[r--]);
        }
    }
};

看了一眼评论区大神的解法，自己尝试：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0,mid = 0,h = nums.size() - 1;
        while(mid <= h)
        {
            if(nums[mid] == 0)
                swap(nums[mid++],nums[l++]);
            else if(nums[mid] == 1)
                mid += 1;
            else
                swap(nums[mid],nums[h--]);
        }
    }
};

运行效率:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sort Colors.
Memory Usage: 8.3 MB, less than 64.12% of C++ online submissions for Sort Colors.

讨论区一个图形化解释：

1 0 2 2 1 0
    ^         ^
    L         H
    M

    Mid != 0 || 2
    Mid++

    1 0 2 2 1 0
    ^ ^       ^
    L M       H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 1 2 2 1 0
      ^ ^     ^
      L M     H

    Mid == 2
    Swap High and Mid
    High--

    0 1 0 2 1 2
      ^ ^   ^
      L M   H

    Mid == 0
    Swap Low and Mid
    Mid++
    Low++

    0 0 1 2 1 2
        ^ ^ ^
        L M H

    Mid == 2
    Swap High and Mid
    High--

    0 0 1 1 2 2
        ^ ^
        L M
          H

    Mid <= High is our exit case

其它解法(单指针，两趟for循环)

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int loc = 0;
        //correct 0 position
        for(int i = 0;i < n;i++)
        {
            if(nums[i] == 0)
                swap(nums[i],nums[loc++]);
        }
        //correct 1 positon
        for(int i = loc;i < n;i++)
        {
            if(nums[i] == 1)
                swap(nums[i],nums[loc++]);
        }
    }
};

运行效率:

Runtime: 4 ms, faster than 47.53% of C++ online submissions for Sort Colors.
Memory Usage: 8.3 MB, less than 64.12% of C++ online submissions for Sort Colors.

另一种计数排序，统计0 1 2个数，然后更新nums

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int zero = 0,one = 0,two = 0;
        for(int i = 0;i < nums.size();i++)
        {
            if(nums[i] == 0)
                zero++;
            else if (nums[i] == 1)
                one++;
            else if(nums[i] == 2)
                two++;
        }
        for(int i = 0;i < zero;i++)
            nums[i] = 0;
        for(int i = 0;i < one;i++)
            nums[zero+i] = 1;
        for(int i = 0;i < two;i++)
            nums[zero+one+i] = 2;
    }
};

运行效率:

Runtime: 4 ms, faster than 47.53% of C++ online submissions for Sort Colors.
Memory Usage: 8.2 MB, less than 88.92% of C++ online submissions for Sort Colors.