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.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

思路：

排序
首先遍歷一遍數(shù)組，分別記錄0,1,2的個(gè)數(shù)，然后更新原數(shù)組，按個(gè)數(shù)分別附上0,1，2，復(fù)雜度為2n

var sortColors = function(nums) {
    var a=0,b=0,c=0;
    for(var i=0;i<nums.length;i++){
        if(nums[i]==0) a++;
        else if(nums[i]===1)b++;
        else if(nums[i]===2)c++;
    }
    for(var i=0;i<a;i++){
        nums[i]=0;
    }
    for(var j=a;j<a+b;j++){
        nums[j]=1;
    }
    for(var i=a+b;i<a+b+c;i++){
        nums[i]=2
    }
};

思路二：題目要求遍歷一遍。
設(shè)置兩個(gè)指針，red指向開(kāi)頭0，blue指向結(jié)尾。從頭遍歷數(shù)組，如果遇到0，交換該值和red指針指向的值，并將red指針后移一位。若遇到2，則交換該值和blue指針指向的值，并將blue前移一位，但是不知道移過(guò)去的是不是0，所以i要減一下重新遍歷換好的一位。

var sortColors = function(nums) {
    var red=0;
    var blue=nums.length-1;
    for(var i=0;i<=blue;i++){
        if(nums[i]===0){
            var temp=nums[i];
                nums[i]=nums[red];
                nums[red++]=temp;
        }else if(nums[i]===2){
            var c=nums[i];
                nums[i]=nums[blue];
                nums[blue--]=c;
                i--;
        }
    }
};