# 143.Sort Colors II

## 1.Description(Medium)

Given an array of\_n\_objects with\_k\_different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.

### Notice

You are not suppose to use the library's sort function for this problem.

k <= n

**Example**

Given colors=`[3, 2, 2, 1, 4]`,`k=4`, your code should sort colors in-place to`[1, 2, 2, 3, 4]`.

[**Challenge**](https://www.lintcode.com/en/problem/sort-colors-ii/#challenge)

A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?

## 2.Code

**Solution 1:** Quick sort 时间复杂度是O(nlogn),空间复杂度是O(Log(N))

```
public void sortColors2(int[] colors, int k) {
        if(colors==null || colors.length==0){
            return;
        }
        quicksort(colors,0,colors.length-1);
    }

    public int partition(int[] colors,int left,int right){
        int i=left;
        int j=right;
        int pivot=colors[(left+right)/2];
        while(i<=j){
            while(colors[i]<pivot){
                i++;
            }
            while(colors[j]>pivot){
                j--;
            }
            if(i<=j){
                int temp=colors[i];
                colors[i]=colors[j];
                colors[j]=temp;
                i++;
                j--;
            }            
        }
        return i;
    }

    public void quicksort(int[] colors,int left,int right){
        int index=partition(colors,left,right);
        if(left<index-1){
            quicksort(colors,left,index-1);
        }
        if(right>index){
            quicksort(colors,index,right);
        }
    }
```

另一种写法简单的快速排序：O(nlogk), the best algorithm based on comparing

<http://www.jiuzhang.com/solutions/sort-colors-ii/>

```
  public void sortColors2(int[] colors, int k) {
        if (colors == null || colors.length == 0) {
            return;
        }
        rainbowSort(colors, 0, colors.length - 1, 1, k);
    }

    public void rainbowSort(int[] colors,
                            int left,
                            int right,
                            int colorFrom,
                            int colorTo) {
        if (colorFrom == colorTo) {
            return;
        }

        if (left >= right) {
            return;
        }

        int colorMid = (colorFrom + colorTo) / 2;
        int l = left, r = right;
        while (l <= r) {
            while (l <= r && colors[l] <= colorMid) {
                l++;
            }
            while (l <= r && colors[r] > colorMid) {
                r--;
            }
            if (l <= r) {
                int temp = colors[l];
                colors[l] = colors[r];
                colors[r] = temp;

                l++;
                r--;
            }
        }

        rainbowSort(colors, left, r, colorFrom, colorMid);
        rainbowSort(colors, l, right, colorMid + 1, colorTo);
    }
```

**Solution 2:** <http://www.cnblogs.com/yuzhangcmu/p/4177326.html>

inplace，并且O(N)时间复杂度的算法。

我们可以使用类似桶排序的思想，对所有的数进行计数。

1. 从左扫描到右边，遇到一个数字，先找到对应的bucket.比如

3 2 2 1 4

第一个3对应的bucket是index = 2 (bucket从0开始计算）

1. Bucket 如果有数字，则把这个数字移动到i的position(就是存放起来），然后把bucket记为-1(表示该位置是一个计数器，计1）。
2. Bucket 存的是负数，表示这个bucket已经是计数器，直接减1. 并把color\[i] 设置为0 （表示此处已经计算过）
3. Bucket 存的是0，与3一样处理，将bucket设置为-1， 并把color\[i] 设置为0 （表示此处已经计算过）
4. 回到position i，再判断此处是否为0（只要不是为0，就一直重复2-4的步骤）。

6.完成1-5的步骤后，从尾部到头部将数组置结果。（从尾至头是为了避免开头的计数器被覆盖）

例子(按以上步骤运算)：

3 2 2 1 4

2 2 -1 1 4

2 -1 -1 1 4

0 -2 -1 1 4

-1 -2 -1 0 4

-1 -2 -1 -1 0

**Solution 3:**

简单的办法可以利用two pass, 相当于counting sort，计数每个color的个数，再依次填入到原来的array中；这种方法空间复杂度为 O(k), 时间复杂度为 O(n)。

**Solution 4:(此方法time limit exceed)**

利用两个指针的方法，设定pl和pr，左右两个指针，初始位置分别为数组两端，pl = 0, pr = colors.length - 1. 同时，由于题目限制条件，已知min和max，因此可以据此作为比较，来决定如何移动pl，pr两个指针。不断对满足min和max条件的colors进行swap，就可以在in-place的条件下，做到sorting colors，这种算法的空间复杂度为O(1), 而时间复杂度：这种方法的时间复杂度为O(n^2): T(n) = T(n - 2) + n。

```
/*Method II:
        *  Each time sort the array into three parts:
        *  [all min] [all unsorted others] [all max],
        *  then update min and max and sort the [all unsorted others]
        *  with the same method.
    */
    public void sortColors22(int[] colors, int k){
        int left=0;
        int right=colors.length-1;
        int i=0;
        int min=1;
        int max=k;
        while(min<max){
            while(i<=right){
                if(colors[i]==min){
                    swap(colors,i,left);
                    i++;
                    left++;
                }else if(colors[i]==max){
                    swap(colors,i,right);
                    right--;
                    //注意这里i不变，因为在要再次判断下交换完的这个数有可能是min
                }else{
                    i++;
                }
            }

            //set i to the first element in unsorted others
            i=left;
            min++;
            max--;           
        }

    }

    public void swap(int[] colors,int i,int j){
        int temp=colors[i];
        colors[i]=colors[j];
        colors[j]=temp;
    }
```