排序算法之计数排序 柔光的暖阳◎ 2022-12-31 01:09 137阅读 0赞 ### \[非比较排序-计数排序\] ### **1.算法思想** * 计数排序要求数据必须是有确定范围的整数,需要定义一个新的数组,新数组的长度是根据原数组最大值和最小值来确定的,该数组用于存放原数组中元素的个数,按找从小到大的顺序依次对原数组的元素赋值 **2.流程分析** 直接上例子:`int[] array = {12, 9, 3, 7, 5, 8, 5}` * 先循环遍历array数组,获取数组元素中的最大值\[12\]和最小值 \[3\] * 定义一个新的数组bucket,长度为\[最大值 - 最小值 + 1\] = **10** * 调用Arrays.fill(bucket, 0)将bucket中的所有元素用0填充,用于**计数** * bucket:\{0,0,0,0,0,0,0,0,0,0\}; * 对应原array数组中的元素如下: * bucket:\{3,4,5,6,7,8,9,10,11,12\}; * 于是引入偏差的概念,**偏差 = 0 - 最小值**; * 因为bucket\[0\]为array中最小元素的值,所以array\[i\]的值对应bucket中的位置为bucket\[array\[i\] - 偏差\],例:array\[0\]对应bucket\[9\],array\[2\]对应bucket\[0\]; * 循环遍历array,bucket中对应进行计数统计元素的个数 * 完成计数后bucket **===>** **\{1,0,2,0,1,1,1,0,0,1\}** * 最后需要对原数组重新排序,即循环遍历array,对每个元素赋值 * bucket是按照从小到大的顺序计数的,计数为0的表示原数组中不存在; * 计数大于1的,每次输出之后需要计数-1,直到计数值为0; * 计数为0的,bucket下标+1,跳过该元素,寻找下一个元素; * 对array元素赋值时,再次用到偏差; * array\[i\] = bucket的下标i - 偏差,相当于下标 + 最小值; **3.动态排序图** ![在这里插入图片描述][20201227000944455.gif] **4.代码实现** public static void countingSort(int[] array) { //最小值 int min = array[0]; //最大值 int max = array[0]; //遍历数组获得最小值和最大值 for (int i = 1; i < array.length; i++) { if (array[i] < min) { min = array[i]; }if (array[i] > max) { max = array[i]; } } //偏差(这个变量至关重要) int bias = 0 - min; //定义一个新的数组 int[] bucket = new int[max - min + 1]; //将数组所有元素用0填充 Arrays.fill(bucket, 0); for (int i = 0; i < array.length; i++) { //对原数组的元素进行计数 bucket[array[i] + bias]++; } int index = 0; int i = 0; while (index < array.length) { //bucket中计数为0,对应的值在原array中不存在 if (bucket[i] != 0) { //对原数组元素按bucket顺序赋值 array[index] = i - bias; bucket[i]--; index++; } else { //跳过原数组不存在的元素 i++; } } } public static void main(String[] args) { int[] array = { 12,9,3,7,5,8,5}; System.out.println("排序前Array:"+ Arrays.toString(array)); countingSort(array); System.out.println("排序后Array:"+ Arrays.toString(array)); /* * 排序前Array:[12, 9, 3, 7, 5, 8, 5] * 排序后Array:[3, 5, 5, 7, 8, 9, 12] */ } **5.总结** 计数排序引入的偏差的概念很重要,bucket数组存放的是array元素的个数,统计元素个数、array遍历赋值这两个步骤只要理解了,计数排序也就很好理解了,通过实际的例子以及代码调试能更快的去理解算法思想。 **理解≠学会,一定要打断点,debug逐步调试,手动敲一遍代码!!!** [20201227000944455.gif]: /images/20221120/cdbb3e1269c5424988b5d23b9558a1e3.png
还没有评论,来说两句吧...