排序算法之计数排序

柔光的暖阳◎ 2022-12-31 01:09 185阅读 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