题目：Sort Colors

一个一维数组只有三个元素要把它排序。

思路1：快速排序。

后面专门总结这个排序算法。

思路2：计数排序。

例如：2 5 3 0 2 3 0 3的数组，先申请长度为6的数组，初始值为0.

然后统计其中0-5的每个数字的个数，

在按照大小顺序输出每个数字统计的次数，即排好序了。

初始：2 5 3 0 2 3 0 3　　统计数组：0 0 0 0 0 0

第1次：2 5 3 0 2 3 0 3　　统计数组：0 0 1 0 0 0

第2次：2 5 3 0 2 3 0 3　　统计数组：0 0 1 0 0 1

第3次：2 5 3 0 2 3 0 3　　统计数组：0 0 1 1 0 1

第4次：2 5 3 0 2 3 0 3　　统计数组：1 0 1 1 0 1

第5次：2 5 3 0 2 3 0 3　　统计数组：1 0 2 1 0 1

第6次：2 5 3 0 2 3 0 3　　统计数组：1 0 2 2 0 1

第7次：2 5 3 0 2 3 0 3　　统计数组：2 0 2 2 0 1

第8次：2 5 3 0 2 3 0 3　　统计数组：2 0 2 3 0 1

最后：0 0 2 2 3 3 3 5

通过统计待排序元素的个数来排序；

它有诸多限制：

1.需要空间O(max-min)；

2.需要元素为int或类似如此能再O(1)的复杂度上找到该元素对应的统计值。

package com.example.medium;/** * 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. * Follow up: * A rather straight forward solution is a two-pass algorithm using counting sort. * First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's. * Could you come up with an one-pass algorithm using only constant space? * @author FuPing * */public class SortColors {    /**     * 对值只有0/1/2的数组排序，可以用计数排序，时间复杂度O(n)     * @param nums     */    public void sortColors(int[] nums) {        int i,sum0 = 0,sum1 = 0;//统计0、1的个数        for(i = 0;i < nums.length;i++){            if(nums[i] == 0)sum0++;            else if(nums[i] == 1)sum1++;        }        for(i = 0;i < sum0;i++){            nums[i] = 0;        }        for(;i < sum1 + sum0;i++){            nums[i] = 1;        }        for(;i < nums.length;i++){            nums[i] = 2;        }    }    /**     * 对值只有三个范围的数组排序，可以用快速排序，时间复杂度O(n)     * @param nums     */    public void sortColors2(int[] nums) {        int left = 0,right = nums.length - 1,middle = 0;        for (int i : nums) {
   //找到2的元素的个数                    if(i > 1)middle++;                }        middle = right - middle;//1从尾部减去2的个数的位置开始        while(left <= middle){            if(nums[right] > 1){
   //尾部大于1                right--;                continue;            }            if(nums[middle] == 1){
   //中间等于1                middle--;                continue;            }            //此时右边的数必定不是2的数,中间的数必定不是1            if(nums[left] > 1){
   //左边大于1                int temp = nums[right];//和右边交换                nums[right--] = nums[left];                nums[left] = temp;            }else if(nums[left] == 1){
   //和中间交换                int temp = nums[middle];                nums[middle--] = nums[left];                nums[left] = temp;            }else{                left++;            }        }    }    public static void main(String[] args) {        // TODO Auto-generated method stub        long startTime = System.currentTimeMillis();        int nums[] = {2,0};        new SortColors().sortColors2(nums);        for (int i = 0; i < nums.length; i++) {            System.out.print(nums[i] + " ");        }        System.out.println();        long endTime = System.currentTimeMillis();        System.out.println("程序运行时间:"+(endTime-startTime) + "ms");    }}