重温计数排序

╰+哭是因爲堅強的太久メ 2023-06-30 01:52 70阅读 0赞

一开始想，对数组进行排序，肯定是要比较的呀，不比较怎么知道大小。直到遇见了计数排序，桶排序，基数排序。真是感叹人类的牛逼。居然还能这样？  
话不多说，下面开始重温计数排序

*  基本思路：先从简单的例子说起。如果给定一个大小为10的数组，并且知道数组里的元素都在0-10的范围内。那么可以建一个长度为11的数组（初始值为0）用于计数。再遍历原始数组，以数组元素的值，作为下标，定位到计数数组中的某个位置，对其值进行加一。也就是把原数组中各个元素出现的次数给统计了一遍。假设原数组为\[2,3,5,9,5,4,1,7,3,2\]。那么得到的计数数组为\[0,1,2,2,1,5,0,1,0,1,0\]。再遍历计数数组，某个下标的元素值为多少，就将下标输出多少次。于是得到\[1,2,2,3,3,4,5,7,9\]
 *  局限性：
    
     *  当数组最大值和最小值相差过大时，不适用（计数数组的空间有很大一部分用不上，很浪费）
     *  当数组元素不是整数时，不适用（计数数组是用下标来代表原数组的值，下标位置的元素值，代表该下标的数字，出现的次数）
 *  优化：  
    朴素版的计数排序，只是对各个元素出现的次数做了简单统计，然后从小到大按出现次数将元素打印了一遍，不能区分相同元素的先后顺序。可以在统计完元素出现次数后，对次数数组进行变形，让次数数组的每个元素，都加上之前的所有元素之和。  
    比如有4个学生
    
     *  小红 95分
     *  小绿 93分
     *  小白 95分
     *  大黄 99分
    
    最大值和最小值的差为 99 - 93 = 6，那么我们创建一个大小为7的数组用于计数，下标0代表93分。于是得到计数数组为\[1,0,2,0,0,0,1\]，之后对计数数组进行变形，每一项都加上前面所有项的和，得到变形后的计数数组 \[1,1,3,3,3,3,4\]。创建一个新的数组用于储存排序结果（长度和原数组一致），然后我们对原数组，从后往前遍历，先取大黄，99分，99-93=6，找到计数数组下标为6的元素，取出，得4，代表大黄排名第4（按从小到大往后排）。于是找到新数组中第四个元素的位置（下标为3），将大黄设置进去，新数组为\[null,null,null,大黄\]，此时将计数数组对应的值-1 ，计数数组为\[1,1,3,3,3,3,3\]，最后一个位置的值变成了3，表示如果再出现99分的同学，即排在第三位。继续遍历原数组，到小白，95分，95-93=2，取计数数组中下标为2的元素，得3，表明95分排第三位，于是对新数组的第三个元素进行设置，得\[null,null,小白,大黄\]，对计数数组对应值减1，得\[1,1,2,3,3,3,3\]。再遍历到小绿，93分，93-93=0，取计数数组下标为0的元素，得1，设置新数组，得\[小绿,null,小白,大黄\]，对计数数组进行减1，得\[0,1,2,3,3,3,3\]。遍历原数组，到小红，95分，95-93=2，取计数数组，得2，设置新数组的第二个位置（下标1），得\[小绿,小红,小白,大黄\]。可见最终的有序数组中，小红和小白的相对位置没有发生变化，是稳定的排序。  
    这种通过对计数数组进行变形的方式，保留了某个元素在整个数组中的位置的信息（比某个元素小的，有多少个元素），并通过对原数组从后往前遍历，并逐步对计数数组进行减一操作，能够保留相同元素的原先的相对位置。

计数排序的时间复杂度是O(n + m)，空间复杂度是O(m)，（n是原数组大小，m是最大值和最小值之差）。最后一步，贴代码，告辞，桶排和鸡排再见！

package sort.core;
    
    
    import lombok.AllArgsConstructor;
    import lombok.Getter;
    import lombok.Setter;
    import org.junit.Test;
    import utils.ArrayUtil;
    
    import java.util.Arrays;
    import java.util.function.IntFunction;
    
    import static utils.ArrayUtil.printArray;
    
    /** Not based on compare **/
    
    /*** * 适用于一定范围内的整数排序，在取值范围不大的情况下，性能比较好 * 局限： * 不适用于小数 * 最大值与最小值差距过大时，也不适用 */
    public class CountSort { 
    	public void countSort(int[] arr){ 
    		if (arr == null || arr.length <= 1)
    			return ;
    		int min,max;
    		min = max = arr[0];
    		for (int i = 1; i < arr.length; i++){ 
    			if (arr[i] < min)
    				min = arr[i];
    			if (arr[i] > max)
    				max = arr[i];
    		}
    		int[] count = new int[max - min + 1];
    		for (int i = 0; i < arr.length; i++){ 
    			count[arr[i] - min]++;
    		}
    
    		int k = 0;
    		for (int i = 0; i < max - min + 1; i++){ 
    			int cnt = count[i];
    			while (cnt > 0){ 
    				arr[k++] = i + min;
    				cnt--;
    			}
    		}
    	}
    
    	/** * 优化，相同元素可以区分 * 从第二个元素开始，每个元素要加上前面所有元素的和 * **/
    
    
    	@Setter
    	@Getter
    	@AllArgsConstructor
    	static class Student{ 
    		private String name;
    		private int score;
    
    		@Override
    		public String toString() { 
    			return "Student{" +
    					"name='" + name + '\'' +
    					", score=" + score +
    					'}'+'\n';
    		}
    	}
    	/** 可以保证稳定 **/
    	/** 时间复杂度为 3n + m , 为 O(n + m) **/
    	/** n为原始数组长度，m为 max - min + 1 **/
    	/** 空间复杂度（不考虑结果数组）：为 O(m) **/
    	public Student[] countSortEnhanced(Student[] arr){ 
    		if (arr == null || arr.length <= 1)
    			return arr;
    		int min,max;
    		min = max = arr[0].getScore();
    		for (int i = 1; i < arr.length ; i++){ 
    			if (arr[i].getScore() < min)
    				min = arr[i].getScore();
    			if (arr[i].getScore() > max)
    				max = arr[i].getScore();
    		}
    		/** 计数 **/
    		int[] scoreCnt = new int[max - min + 1];
    		for (int i = 0; i < arr.length; i++){ 
    			scoreCnt[arr[i].getScore() - min]++;
    		}
    		/** 变形 **/
    		for (int i = 0; i < max - min + 1; i++){ 
    			if (i == 0)
    				continue;
    			scoreCnt[i] += scoreCnt[i - 1];
    		}
    		/**对原数组从后往前遍历**/
    		Student[] sortedArr = new Student[arr.length];
    		for (int i = arr.length - 1; i >= 0; i--){ 
    			/** 注意排名第一，要插入到第0号位置，所以用前置--，而不是后置-- **/
    			int pos = --scoreCnt[arr[i].getScore() - min];
    			sortedArr[pos] = arr[i];
    		}
    		return sortedArr;
    	}
    
    	@Test
    	public void test2(){ 
    		Student[] arr = Arrays.asList(
    				new Student("yogurt",95),
    				new Student("amber",94),
    				new Student("lily",96),
    				new Student("potter",99),
    				new Student("harry",94),
    				new Student("tom",99)
    		).stream().toArray(Student[]::new);
    
    		Student[] sorted = countSortEnhanced(arr);
    
    		printArray(sorted);
    	}
    
    	@Test
    	public void test(){ 
    		int[] arr = { 2,-8,5,12,1,3,4,9,10,5,7,6};
    		countSort(arr);
    		printArray(arr);
    	}
    }