颜色分类

    /*** 颜色分类：计数排序* 时间复杂度：O(n)* 空间复杂度:O(1)* @param nums*/public void sortColors(int[] nums) {//存放0,1,2这三个元素的频率int[] color = {0,0,0};for(int i=0;i<nums.length;i++){if(nums[i] >=0 && nums[i]<=2){color[nums[i]]++;}}//把0,1，2放回nums数组int index = 0;for(int i=0;i<color[0];i++){nums[index] = 0;index++;}for(int i=0;i<color[1];i++){nums[index] = 1;index++;}for(int i=0;i<color[2];i++){nums[index] = 2;index++;}}

 /*** 颜色分类：三路快排:设置两个指针分别指向0的最后一个元素和2的第一个元素* 时间复杂度：O(n)* 空间复杂度:O(1)* 遍历整个数组一遍* @param nums*/public void sortColors2(int[] nums) {//nums[0...zero]==0//nums[zero+1...i-1]==1//nums[two...n-1]==2int zero  =-1;int two =nums.length;for(int i = 0;i<two;){if(nums[i] == 1){i++;}else if(nums[i] == 2){two --;int temp = nums[two];nums[two] = nums[i];nums[i] = temp;//i不需要++}else if(nums[i] == 0){zero ++;int temp = nums[zero];nums[zero] = nums[i];nums[i] = temp;//考察下一个元素i++;}}}