学步园

1.1      Sort Colors  单词遍历 给0，1，2排序

Given an array with n objectscolored red, white or blue, sort them so that objects of the same color areadjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2to represent the color red, white, and blue respectively.

Note:
You are not suppose to use thelibrary's sort function for this problem.

Follow up:
A rather straight forwardsolution is a two-pass algorithm using counting sort.
First, iterate the arraycounting number of 0's, 1's, and 2's, then overwrite array with total number of0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithmusing only constant space?

package Array;

import java.util.Arrays;

/**
 * @Title: SortColors.java
 * @Package Array
 * @Description: TODO
 * @author nutc
 * @date 2013-9-6 下午2:39:08
 * @version V1.0
 */
public class SortColors {

	public static void main(String args[]) {
		SortColors s = new SortColors();

		int[] a = { 2,0};
		s.sortColors(a);
		System.out.println(Arrays.toString(a));
	}

	public void sortColors(int[] A) {
		if (A == null)
			return;

		int i = 0, j = A.length - 1, k = 0;

		 while (i < A.length && A[i] == 0)
		 i++;
		 while (j >= 0 && A[j] == 2)
		 j--;
		k = i;
		while (k <= j && i <= j) {

			if (A[k] == 0) {
				if (k > i) {
					int temp = A[i];
					A[i] = A[k];
					A[k] = temp;
					i++;
				}else{
					k++;
				}
			} else if (A[k] == 2) {
				int temp = A[j];
				A[j] = A[k];
				A[k] = temp;
				j--;
			} else {
				k++;
			}
		}

	}

}