Sort Colors @leetcode

SortColors.java

package leetcode;

/**
 * Solution: Three pointer-- O(n) one pass. Counting Sort -- O(n) two pass, Bubble Sort -- O(n^2)
 * At first, I use general two point, i and tail. But it doesn't work. Can't handle "1" easily.
 * redIndex and blueIndex is a smart way.
 * 
 * Reference: http://fisherlei.blogspot.com/2013/01/leetcode-sort-colors.html
 * @author jeffwan
 * @date Apr 2, 2014
 */
public class SortColors {	
	/*
	 * Define two pointer, redPointer, bluePointer. O(n) Time, O(1) Space.
	 * scan from i to blueIndex.(i could be equlas to blueIndex!)
	 * 1. 0 -> move to redIndex. redIndex++, i++
	 * 2. 1 -> i++
	 * 3. 2 -> move to blueIndex. blueIndex--;
	 * 4. We can't i++ after swap with blueIndex, because we don't know if new number is 0, 1 ,2. But we can i++ fater swap with 
	 * redIndex, because all redIndex points to 0(except for 1st time).
	 */
	public void sortColors(int[] A) {
		if (A == null || A.length == 0) {
			return;
		}
		
		int redIndex = 0;
		int blueIndex = A.length - 1;
		int i = 0;
		
		while (i <= blueIndex) {
			if (A[i] == 0) {
				swap(A, redIndex, i);
				i++;
				redIndex++;
			} else if (A[i] == 1) {
				i++;
			} else {
				swap(A, blueIndex, i);
				blueIndex--;
			}
		}
	}
	
	private static void swap(int[] A, int i, int j) {
		int temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}

	/*
	 *  Solution provided by problem. -- Counting Sort. O(n) --> two pass
	 *  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.
	 */
	public void sortColors1(int[] A) {
		if (A == null || A.length == 0) {
			return;
		}
		
		int[] count = new int[3];
		for (int i = 0; i < A.length; i++) {
			if (A[i] == 0) {
				count[0]++;
			} else if (A[i] == 1) {
				count[1]++;
			} else {
				count[2]++;
			}
		}
		
		int i = 0;
		for (int k = 0; k < count.length; k++) {
			while (count[k] > 0) {
				A[i] = k;
				i++; 
				count[k]--;
			}
		}
	}
	
	// Brute Force. Bubble Sort O(n^2)
	public void sortColors2(int[] A) {
		if (A == null || A.length == 0) {
			return;
		}
		
		for (int i = 0; i < A.length - 1; i++) {
			for (int j = i + 1; j < A.length; j++) {
				if (A[i] > A[j]) {
					int temp = A[j];
					A[j] = A[i];
					A[i] = temp;
				}
			}
		}
    }
}