https://oj.leetcode.com/problems/sort-colors/

http://blog.csdn.net/linhuanmars/article/details/24286349

public class Solution {
    public void sortColors(int[] A) 
    {
        // Solution A:
        sortColors_CountColor(A);
        
        // Solution B:
        // sortColors_MergeSort(A, 0, A.length - 1);
    }
    
    ///////////////////////////
    // Solution A: CountColor
    //
    private void sortColors_CountColor(int[] A)
    {
        int[] c = new int[3];
        for (int i : A)
        {
            c[i - 0] ++;
        }
        
        int count = 0;
        int index = 0;
        for (int i = 0 ; i < A.length ; i ++)
        {
            if (count == c[index])
            {
                count = 0;
                index++;
                i--;
                continue;
            }
            
            A[i] = index;
            count ++;
        }
    }

    ///////////////////////////
    // Solution B: MergeSort
    //
    private void sortColors_MergeSort(int[] A, int low, int high)
    {
        if (low >= high)
            return;
        
        int mid = (low + high) / 2;
        sortColors_MergeSort(A, low, mid);
        sortColors_MergeSort(A, mid + 1, high);
        
        // Merge
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;
        while (k < temp.length)
        {
            int a = i <= mid ? A[i] : Integer.MAX_VALUE;
            int b = j <= high ? A[j] : Integer.MAX_VALUE;
            if (a < b)
            {
                temp[k] = a;
                i++;
            }
            else
            {
                temp[k] = b;
                j ++;
            }
            k ++;
        }
        for (int m = low ; m <= high ; m ++)
        {
            A[m] = temp[m - low];
        }
    }
}

[LeetCode]75 Sort Colors