75. Sort Colors

We traverse the array and use two variables:

1. zeroIndex to indicate the index where we should put 0 at
2. twoIndex to indicate the index where we should put 2 at

If current element a[i] is 0, we swap a[i] and a[zeroIndex], if a[i] is 2, we swap a[i] and a[twoIndex], if a[i] is one, we do nothing and continue to process next element.

public void sortColors(int[] nums) {
    int zeroIndex = 0, twoIndex = nums.length - 1, i = 0;
    while( i <= twoIndex ) {
	if( nums[i] == 0 ) 
	    swap(nums, zeroIndex++, i++);
	else if( nums[i] == 2)
	    swap(nums, twoIndex--, i);    
	else
	    i++;
    }
}

public void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}