Sort Colors

Based on the "follow up", this solution is the so-called "one pass with constant space" algorithm.

last0Idx, last1Idx, last2Idx are used to store the index of last 0, 1, and 2, so that when one color is met during traversal, this element can be inserted after one of these indexes. That's why above 3 indexes starts from -1.

After taking a look at "Discuss" community, I find one answer by xianlei, whose idea is similar to mine, but better.
// My solution
public class Solution {
    public void sortColors(int[] A) {
        int last0Idx = -1;
        int last1Idx = -1;
        int last2Idx = -1;
        int i = 0;
        for(;i < A.length; i ++){
            if(A[i] == 0){
                insert(A,last0Idx,i);
                last0Idx++;
                last1Idx++;
                last2Idx++;
            }
            else{
                if(A[i] == 1){
                    insert(A,last1Idx,i);
               
                    last1Idx++;
                    last2Idx++;                  
                }
                else{
                    insert(A,last2Idx,i);

                    last2Idx++;                  
                }
            }

        }
    }
   
    public void insert(int[] A, int insertIdx, int crntIdx){
                int tmp = A[crntIdx];
                for(int i = crntIdx-1;i>=insertIdx+1;i-- ) A[i+1] = A[i];
                A[insertIdx+1] = tmp;
    }
   
}


// By xianlei

public void sortColors(int[] A) { int i=-1, j=-1, k=-1; for(int p = 0; p < A.length; p++) { if(A[p] == 0) { A[++k]=2; A[++j]=1; A[++i]=0; } else if (A[p] == 1) { A[++k]=2; A[++j]=1; } else if (A[p] == 2) { A[++k]=2; } } }