计数排序详解

1、什么是计数排序？

        计数排序是一种非比较排序，其核心是将序列中的元素作为键存储在额外的数组空间中，而该元素的个数作为值存储在数组空间中，通过遍历该数组排序。

2、计数排序的应用场景

计数排序适用于：

        1、序列中最大值和最小值之间的差值不能过大，这主要是防止建立数组时造成内存的浪费。

        2、序列中存在的元素是整数，因为我们使用的是该元素作为键存储在额外的数组空间中，如果不是整数，不能作为键。

3、计数排序的思想

        计数排序的核心是：利用数组的索引是有序的，通过将序列中的元素作为索引，其个数作为值放入数组，遍历数组来排序。

4、计数排序的步骤

计数排序的朴素方法步骤：

        1、从无序数组中取出最大值max，新建一个长度为max+1的数组。

        2、遍历无序数组，取其中元素作为新建数组的索引，存在一个则新数组该索引所在的值自增。

        3、遍历新数组，当存在不为0的元素，取该元素的索引放入最终数组，并且该元素自减，直到为0，返回最终数组。

该方法存在的问题：

        1、新建一个长度为max+1的数组会造成内存的浪费，比如元素为{400，405，410}则新建数组的长度为411，这会使前面的0 ~ 400索引没用，造成内存浪费。

        2、其将元素作为键，将个数作为值放入新的数组中，但是如果存在相同的元素，我们只统计其个数，其顺序无法确定，是不稳定的。

解决方法：

        1、问题1的解决方法是：取数组中的最大值max和最小值min，新建(max-min +1)长度的数组，数组的元素存放在新数组中的（arr[i]-min）索引处。

        2、问题2的解决方法是：新建一个统计数组，其长度为(max-min +1)，其索引存放的是新数组该索引之前元素的和，这个和表示的是该索引（该元素）在原数组中的排序顺序，就是排第几。

计数排序的最终步骤：

        1、取无序数组arr中的最大值max和最小值min，新建(max-min +1)长度的数组newArr和长度为(max-min +1)的统计数组countArr。

        2、遍历原数组arr，将其值作为newArr的键，元素的个数作为值存放在该键处。

        3、遍历newArr，使统计数组countArr和newArr相同索引处存放的是newArr该索引之前元素的和。

        4、新建一个最终数组result，反向遍历原数组，取原数组的值arr[i]-min作为索引，从统计数组countArr取出该索引的值减1，作为最终数组result的索引，值为原数组的arr[i]，同时统计数组该索引处值减1，遍历结束后，最终数组result为排序后的数组。

5、计数排序的Java代码

        朴素的计数排序Java代码：

public class CountSort {
 
    public static void main(String[] args) {
        int[] arr = {1, 4, 9, 2, 5, 3, 7, 6, 22, 23, 15, 24, 0,
                3, 4, 5, 2, 3, 5, 12, 1, 3, 4, 2, 1,
                3, 45, 1, 1};
        // 计数排序
        countSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    private static void countSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // 用于获取最大值
        int max = arr[0];
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
        }
        // 用数组中的值作为索引，个数作为值
        int[] newArr = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            newArr[arr[i]]++;
        }
        int j = 0;
        // 遍历并且重新覆盖该值
        for (int i = 0; i < newArr.length; i++) {
            for (int i1 = 0; i1 < newArr[i]; i1++) {
                arr[j++] = i;
            }
        }
    }
 
}

        最终的计数排序Java代码：

public class CountSort {
 
    public static void main(String[] args) {
        int[] arr = {1, 4, 9, 2, 5, 3, 7, 6, 22, 23, 15, 24, 0, 3,
                4, 5, 2, 3, 5, 12, 1, 3, 4, 2, 1,
                3, 45, 1, 1};
        // 计数排序
        int[] ints = countSort1(arr);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }
    }
 
    private static int[] countSort1(int[] arr) {
        // 检测数据
        if (arr == null || arr.length == 0) {
            return arr;
        }
        // 缩短不必要的长度，获取最大和最小值
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        // 用数组中的值作为索引，个数作为值
        int[] newArr = new int[(max - min + 1)];
        // 用于记录当前数据排在第几位
        int[] countArr = new int[newArr.length];
        for (int i = 0; i < arr.length; i++) {
            newArr[arr[i] - min]++;
        }
        // 统计数组，记录后面的元素等于前面的元素之和
        for (int i = 0; i < newArr.length; i++) {
            if (i == 0) {
                countArr[i] = newArr[i];
                continue;
            }
            countArr[i] = newArr[i] + countArr[i - 1];
        }
        // 最终结果
        int[] result = new int[arr.length];
        // 反向遍历
        for (int i = arr.length - 1; i >= 0; i--) {
            // 将数据放入指定的位置中,统计数组中记录的是元素排在第几位
            result[countArr[arr[i] - min] - 1] = arr[i];
            // 排列一个后，就减少一个
            countArr[arr[i] - min]--;
        }
        return result;
    }
}

6、计数排序的总结

        计数排序是非比较排序，时间复杂度是O(n+k)，空间复杂度是O(k)，是稳定算法。（n表示的是数组的个数，k表示的max-min+1的大小）

时间复杂度是O(n+k)：通过上面的代码可知最终的计数算法花费的时间是3n+k，则时间复杂度是O(n+k)。

空间复杂度是O(k)：如果出去最后的返回数组，则空间复杂度是2k，则空间复杂度是O(k)

稳定算法：由于统计数组可以知道该索引在原数组中排第几位，相同的元素其在原数组中排列在后面，其从原数组的后面遍历，其在最终数组中的索引也在后面，所以相同的元素其相对位置不会改变。

7、计数排序的类比

        计数排序的重点是：将序列中的元素作为键存储在额外的数组空间中，通过遍历来排序。类似于：我要给一系类弹珠从小到大排列，我可以拿一个模具，模具上有从小到大的孔洞，我把弹珠放进孔洞中，最后只要从模具中从小到大的孔洞中倒出弹珠即可。