【算法Algorithm】计数（Count）排序

算法思想

计数排序是非比较排序，即没有像arr[i] < arr[i + 1]这样的比较。

该算法适用于数量大且值的范围小的待排序数组，例如：待排序数组长度是1w（或10w，100w），但数组中值的范围在[0,100]；所以，得明确待排序数组中数据的范围

算法思想：

引入一个计数数组，该数组的作用就是记录待排序数组中某一个值出现的次数（待排序数组中的值对应计数数组的下标）；循环待排序数组的每一个值，计数数组的下标为该值时加1；然后循环计数数组，根据每个下标值的数量列出下标值，从而得到排好序的数组。

代码实现

简单实现

public static void main(String[] args) { // 构造一个待排序数组 int[] arr = {1, 2, 5, 9, 7, 6, 4, 0, 1, 5, 4, 9, 5, 1, 7, 1, 5, 8, 9}; int[] result = sort(arr); System.out.println("最终结果：" + Arrays.toString(result)); } private static int[] sort(int[] arr) { // 定义一个新的结果数组，其长度和待排序数组一样 int[] result = new int[arr.length]; // 定义一个计数数组，记录待排序数组中每个值出现的次数；数组长度10是指待排序数组中的数都在[0,10]这个范围内 int[] count = new int[10]; // 计数 for (int i = 0; i < arr.length; i++) { // arr[i]是待排序数组中的数值，其“正好”对应计数数组的下标；存在相同的数，就加1 count[arr[i]]++; } System.out.println("计数数组的结果：" + Arrays.toString(count)); // 排列 int j = 0; for (int i = 0; i < count.length; i++) { // count[i]--是指每排列一个值，那么相同值的计数减1，直到相同的数排列完 while (count[i]-- > 0) { // i就是待排序数组中的数 result[j++] = i; } } }

以上算法实现是不稳定的，而稳定算法的实现需要累加和倒序排列。如下

private static int[] sort(int[] arr) { // 定义一个新的结果数组，其长度和待排序数组一样 int[] result = new int[arr.length]; // 定义一个计数数组，记录待排序数组中每个值出现的次数；数组长度10是指待排序数组中的数都在[0,10]这个范围内 int[] count = new int[10]; // 计数 for (int i = 0; i < arr.length; i++) { // arr[i]是待排序数组中的数值，其“正好”对应计数数组的下标；存在相同的数，就加1 count[arr[i]]++; } System.out.println("计数数组的结果" + Arrays.toString(count)); // 累加，累加的目的是确定待排序数组中的数在排列时的索引位置 for (int i = 1; i < arr.length; i++) { // 索引1的数加它前面的数，索引2的数加它前面的数... count[i] += count[i - 1]; } System.out.println("计数数组累加后的结果" + Arrays.toString(count)); // 倒序排列 for (int i = arr.length - 1; i >= 0; i--) { /* count[arr[i]]是指i这个数对应累加后的值 --count[arr[i]]是指i这个数在排列中的索引位置，先减是为了得到索引，也避免了数组越界 不用担心result[]数组下标越界（变成负值），因为每一个不相等的arr[i]都对应一个累加值 */ result[--count[arr[i]]] = arr[i]; } }

特殊情况：如果待排序数组中数据的范围不是从0开始，例如int[] arr = {50,90,100,67,85,51,72,90,58,99}，数据的范围是[50,100]

简单实现

private static int[] sort(int[] arr) { int[] result = new int[arr.length]; int[] count = new int[10]; for (int i = 0; i < arr.length; i++) { // 让arr[i]减去区间范围下限，使arr[i]的值正好对应计数数组下标 arr[i] -= 50; count[arr[i]]++; } int j = 0; for (int i = 0; i < count.length; i++) { while (count[i]-- > 0) { // 把减去的下限再加回去 result[j++] = i + 50; } } }

稳定实现

private static int[] sort(int[] arr) { int[] result = new int[arr.length]; int[] count = new int[10]; for (int i = 0; i < arr.length; i++) { // 只做这一处修改即可 arr[i] -= 50; count[arr[i]]++; } for (int i = 1; i < arr.length; i++) { count[i] += count[i - 1]; } for (int i = arr.length - 1; i >= 0; i--) { result[--count[arr[i]]] = arr[i]; } }

复杂度和稳定性

时间复杂度

最好时间复杂度：O(n+k)最坏时间复杂度：O(n+k)平均时间复杂度：O(n+k)

空间复杂度：O(n+k)

稳定性：稳定（可以稳定）

参考文章

https://www.runoob.com/w3cnote/counting-sort.html