Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

题目分析

一看到题马上想到了快排的想法，先将所有的2移到最后，再排序0和1.

代码

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

一步到位

直接把所有的2移到最后，0移到最前，1自然在中间，前面的思路是对的，但是没有在多往更深的方向想。

    class Solution {
    public:
        void sortColors(int A[], int n) {
            int second=n-1, zero=0;
            for (int i=0; i<=second; i++) {
                while (A[i]==2 && i<second) swap(A[i], A[second--]);
                while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
            }
        }
    };