題目
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?
分析
給定一組0,1,2的亂序票彪，要求先列0晰筛，在列出1，之后列出2亿乳∥茄酰可以使用統(tǒng)計(jì)的方法算出依次有多少個僚匆，然后輸出即可憋飞。題目提示可以有一遍遍歷即可實(shí)現(xiàn)的方法他炊。于是可以設(shè)想有兩個指針争剿，p指向前面0和1的間隙，q指向與1和2的間隙痊末。遍歷過程中發(fā)現(xiàn)0和2后就向前后指針位置分別交換蚕苇，同時更新指針的位置，直到遍歷后i==q凿叠。這樣所有的0都在p指針之前涩笤，所有的2都在q指針之后，那么1就在中間盒件，于是排序完畢蹬碧。無多余內(nèi)存空間使用。
void sortColors(int* nums, int numsSize) {
int p=0,q=numsSize-1;
for(int i=0;i<numsSize&&i<=q;i++)
{
if(nums[i]==0)
{
if(p!=i)
{
int temp=nums[i];
nums[i]=nums[p];
nums[p]=temp;
}
p++;
}
else if(nums[i]==2)
{
int temp=nums[i];
nums[i]=nums[q];
nums[q]=temp;
q--;
i--;
}
//printf("%d %d\n",p,q);
//for(int j=0;j<numsSize;j++)
// printf("%d ",nums[j]);
//printf("\n");
}
}
