题目

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。可以使用统计的方法算出依次有多少个，然后输出即可。题目提示可以有一遍遍历即可实现的方法。于是可以设想有两个指针，p指向前面0和1的间隙，q指向与1和2的间隙。遍历过程中发现0和2后就向前后指针位置分别交换，同时更新指针的位置，直到遍历后i==q。这样所有的0都在p指针之前，所有的2都在q指针之后，那么1就在中间，于是排序完毕。无多余内存空间使用。

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");
    }
}