75 Sort Colors

https://leetcode.com/problems/sort-colors/#/description

Given an array withnobjects 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?

分析及代码

方法是这样的，维持两个指针，idx0指向已排好序的部分中最后一个0的后一位，idx1指向已排好序部分的最后一个1的后一位

如果碰到的是1，那么需要把现有的2(if any)往后移一位，给新的1提供一个空位，然后把1填进去，如图

//发现一个新的1
0000...0001111...111222...1unsortedpart
          ^         ^     ^
        idx0       idx1   i

//把2往后移动一位（在i位填上2），这样，曾经的idx1的位置上所在的那个2就没用了，相当于空出来了，  
0000...0001111...111222...2unsortedpart
          ^         ^     ^
        idx0       idx1   i

//于是可以在这一位上填一个1
0000...0001111...111122...2unsortedpart
          ^         ^     ^
        idx0       idx1   i

//所以idx1要往后移一位，i当然也往后移了一位
0000...0001111...111122...2unsortedpart
          ^          ^     ^
        idx0        idx1   i

碰到的是0同理

//发现一个新的0，我们目标是在idx0的位置上挤进一个新的0，就需要整个往后挪动一格
0000...0001111...111222...0unsortedpart
          ^         ^     ^
        idx0       idx1   i

//把2往后移动一位（在i位填上2），这样，曾经的idx1的位置上所在的那个2就没用了，相当于空出来了，  
//于是可以在这一位上填一个1       
//所以idx1要往后移一位，i当然也往后移了一位
0000...0001111...111112...2unsortedpart
          ^          ^    ^
        idx0        idx1  i
//这时，idx1上的1就没用了，被空出来了，填入0
0000...0000111...111112...2unsortedpart
          ^          ^    ^
        idx0        idx1  i
//idx0,idx1,i都往后移动一位
0000...0000111...111112...2unsortedpart
           ^          ^    ^
         idx0        idx1  i

代码是

public void sortColors(int[] nums) {
        if(nums == null || nums.length == 0) {
            return;
        }
        int index0 = 0;
        int index1 = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                nums[i] = 2;
                nums[index1++] = 1;
                nums[index0++] = 0;
            } else if(nums[i] == 1) {
                nums[i] = 2;
                nums[index1++] = 1;
            }
        }
    }
}