Sort Colors

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?

Solution1: one-pass, 2 pointers
两个指针，一个指在当前0的最后一个下标，另一个是指在当前1的最后一个下标（2不需要指针因为剩下的都是2了）。进行一次扫描，如果遇到0就两个指针都前进一步并进行赋值，如果遇到1就后一个指针前进一步并赋值。
时间复杂度是O(n)，只是只需要一次扫描，空间上是O(1)（如果颜色种类是已知的话）。

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length == 0)
            return;
        
        int index0 = 0;  //points to last 0
        int index1 = 0;  //points to last 1
        for(int i = 0; i < A.length; i++) {
            if(A[i] == 0) {  //if 0, move index1 and index0 one step forward and assign the value
                A[i] = 2;
                A[index1] = 1;
                index1++;
                A[index0] = 0;
                index0++;
            }else if(A[i] == 1) {  //if 1, move index1 one step forward and assign the value
                A[i] = 2;
                A[index1] = 1;
                index1++;
            }
        }
    }
}

Solution2: One-pass algorithm, 3 pointers

public class Solution {
    public void sortColors(int[] A) {
        int i = 0, j = A.length - 1;
        
        while(i < A.length && A[i] == 0)
            i++;
        while(j >=0 && A[j] == 2)
            j--;
        
        int cur = i;
        while(cur <= j) {
            if(A[cur] <= A[i]) {
                swap(A, cur, i);
                while(i < j && A[i] == 0) {
                    i++;
                    cur = i;
                }
            }
            if(A[cur] > A[j]) {
                swap(A, cur, j);
                while(j > 0 && A[j] == 2) {
                    j--;
                }
            }else {
                cur++;
            }
        }
    }
    
    public void swap(int[] A, int a, int b) {
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
}