解题思路

计数排序

统计每一个数字出现的次数，即0、1、2出现的次数。然后按顺序放回数组。即计数排序的思路，适用于元素个数非常有限的排序算法。

   public void sortColors(int[] nums) {
        //长度为3的count数组记录每个数字出现的次数
        int[] count = {0,0,0};
        for(int i:nums){
            count[i]++;        //遍历统计每个数字出现的次数
        }
        //重新写回数组
        int index = 0;
        for(int i=0;i<count[0];i++)
            nums[index++]=0;
        for(int i=0;i<count[1];i++)
            nums[index++]=1;
        for(int i=0;i<count[2];i++)
            nums[index++]=2;
    }
//time O(n)
//space O(1)

三路快排

确保0出现开始的位置，2出现在尾部的位置，1出现在0之后的位置

• arr[0,…zero]记录已经放好位置的0的个数，arr[two….n-1]记录已经放好位置的2的数组。
• i元素用来进行遍历，确保arr[zero+1…i-1]的位置上都是1.
• e是当前扫描到的元素，如果是1，直接纳入1的数组中，i++
• 如果是2，与two数组前面的元素进行交换，并且two—。
• 如果是0，把zero+1的位置的元素与当前元素交换位置即可，zero++,i++

public void sortColors(int[] nums) {
        int zero = -1;                //因为arr[0,,,zero]表示0的部分，所以初始化为-1
        int two = nums.length;      //因为arr[two,...n-1]表示2的部分，所以初始化为 nums.lengt
        for(int i=0;i<two;){
            if(nums[i]==1){
                i++;
            }else if(nums[i]==0){
                zero++;
                swap(nums,zero,i);
                i++;
            }else{
                two--;
                swap(nums,two,i);
            }
        }
    }
    public void swap (int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }