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.

Naive Way: I think this question is among the highest level questions for using Two Pointers. The question generally means there is an array with 0,1,2s with no order, we are going to grab all 0s first, and then all 1s and then all 2s and set them in the original array.
It would be simple if there is only 0s and 1s. We can use the Two Pointers way, use a pointer to denote current position, another for increment index. Each we come across a 0, set num[current++] = 0, and then set the remaining to be 1.
Considering the same approach, we set a pointer for 0, a pointer for 1, then the remaining positions will be 2. Each time we come across a 0, set num[pointer0++] = 0, and pointer1++. Each time we come across a 1, set pointer1++. And the final cut of the array will be [0,pointer0]->0, [pointer1,pointer1]->1, [pointer1, pointer2]->2.

 public class Solution {  
   public void sortColors(int[] A) {  
     int p0 = 0, p1 = 0;  
     for(int i = 0;i < A.length;i++){  
       if(A[i] == 0){  
         A[p0++] = 0;  
         p1++;  
       }  
       if(A[i] == 1)  
         p1++;  
     }  
     for(int i = p0;i < p1;i++) A[i] = 1;  
     for(int i = p1;i < A.length;i++) A[i] = 2;  
   }  
 }  

The above solution achieves O(1) space and O(n) time complexity, which is good given this problem.
However, the highest level for doing this question is not only achieve best space and run time, but also achieve best in algorithm level. Is there any difference between O(5n) and O(200n)? Is is better if we can scan it once to get same effect of scanning twice.

In the above solution, we actually scan the entire array twice. There is an obvious redundancy that we didn't fully make use of the core of two pointer-> cover/replace. Use a valid value to replace the incorrect value. Can we also write the array when encountering 1s and 2s?

 public class Solution {  
   public void sortColors(int[] A) {  
     int p[] = new int[3];  
     for(int i = 0;i < A.length;i++){  
       if(A[i] == 2){  
         A[p[2]++] = 2;  
       }else if(A[i] == 1){  
         A[p[2]++] = 2;  
         A[p[1]++] = 1;  
       }else{  
         A[p[2]++] = 2;  
         A[p[1]++] = 1;  
         A[p[0]++] = 0;  
       }  
     }  
   }  
 }  

And the solution can be generalized to k colors.

 public class Solution {  
   public void sortColors(int[] A) {  
     int k = 3;  
     int p[] = new int[k];  
     for(int i = 0;i < A.length;i++){  
       int t = A[i];  
       for(int j = k-1; j >= t;j--)  
         A[p[j]++] = j;  
     }  
   }  
 }  

Improved Way: Also, there is another solution that is able to achieve sort color in one pass. It uses swapping. And since it's only 0,1,2. Swapping can be done by simple assign value.

 public class Solution {  
   public void sortColors(int[] A) {  
     int p0 = 0, p1 = 0, p2 = A.length-1;  
     while(p1 <= p2){  
       if(A[p2]==2)  
         p2--;  
       else{  
         if(A[p1]==2)  
           swap(A, p1, p2);  
         else if(A[p1]==0)  
           swap(A, p0++, p1++);  
         else  
           p1++;  
       }  
     }  
   }  
   private void swap(int[] A, int x1, int x2){  
     int temp = A[x1];  
     A[x1] = A[x2];  
     A[x2] = temp;  
   }  
 }