Sort Colors II

不得不说简直太愚蠢了，本来以为是多么高深的算法，结果就是一个quicksort
Time Complexity O(nlogk)
这里pivot很有意思，因为已经知道输入是连续的1-k所以很容易可以选出一个绝对的mid就是 (1 + k) / 2，这样可以保证每一层用O(n)的时间把一个#k可能性的问题分成2个#k/2的问题。最终到达base case只需要logk层。所以时间复杂度是O(nlogk)
还有别的解法暂时没有心情想。不过quicksor应该是最优解
class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        // write your code here
          if (colors == null || colors.length == 0) return;
          sortColors2(colors, 0, colors.length - 1, 1, k);
    }
    private void sortColors2(int[] colors, int start, int end, int minColor, int maxColor) {
        if (minColor == maxColor) return;
        int pivotColor = (minColor + maxColor) / 2;
        int left = start;
        int right = end;
       
        while (left <= right) {
            while (left <= right && colors[left] <= pivotColor) left++;
            while (left <= right && colors[right] > pivotColor) right--;
            if (left <= right) {
                int temp = colors[left];
                colors[left] = colors[right];
                colors[right] = temp;
                left++;
                right--;
            }
        }
        sortColors2(colors, start, left - 1, minColor, pivotColor);
        sortColors2(colors, left, end, pivotColor + 1, maxColor);
       
    }
}