[Leetcode] 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的方法是扫描两遍，第一遍记录0，1，2的个数，然后第二遍扫描的时候按照个数来存值。另外一种方法是使用一种叫做三路归并的技术，这种技术在快速排序中经常用到，以此来提高快排在数组中存在大量重复元素的时候的效率。

    public void sortColors(int[] A) {
        int start = 0, current = 0, back = A.length - 1;
        // start position of 1s if exist, current position, the first element before continue 2s
        while(current <= back) {
            if(A[current] == 1)
                current++;
            else if(A[current] == 0) {
                A[current] = A[start]; // current and start might be the same
                A[start] = 0;
                start++; current++;
            }
            else {
                A[current] = A[back];
                A[back] = 2;
                back--;
            }
        }
    }