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.
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的個數(shù)，然后更新原數(shù)組了赌，按個數(shù)分別附上0,1扰柠，2究履，復雜度為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
}
};
思路二：題目要求遍歷一遍。
設置兩個指針，red指向開頭0塞关，blue指向結(jié)尾姐扮。從頭遍歷數(shù)組絮供，如果遇到0，交換該值和red指針指向的值茶敏，并將red指針后移一位壤靶。若遇到2，則交換該值和blue指針指向的值惊搏，并將blue前移一位贮乳，但是不知道移過去的是不是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--;
}
}
};
