Sort Colors II

思路：
才有quicksort的思想，先求出一个midcolor =(1+k)/2。把小于等于mid放左边，大于mid放右边。然后再分解。
实现：
代码如下：

 public 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  
      rainbowSort(colors, 0, colors.length - 1, 1, k);  
   }  
   private void rainbowSort(int[] colors,  
                int left,  
                int right,  
                int fromColor,  
                int toColor) {  
       if(fromColor == toColor)  
       return;  
       if(left >= right)  
       return;  
     int midColor = (fromColor + toColor) / 2;  
     int index = left;  
     for(int i = left; i <= right; i++)   
     {  
       if(colors[i] <= midColor) {  
         swap(colors, i, index++);  
       }  
     }  
     rainbowSort(colors, left, index - 1, fromColor, midColor);  
     rainbowSort(colors, index, right, midColor + 1, toColor);  
   }  
    private void swap(int[] a, int i, int j) {  
     int tmp = a[i];  
     a[i] = a[j];  
     a[j] = tmp;  
  }  
 }  

这个普通quicksort不同， pivot没有index，所以判断条件是colors[i] <= midColor。普通的quicksort在每一次partition有一次swap, 把pivot放到中间去。