目录

计数排序

lienhui68 收录于技术

2020-06-12 约 712 字预计阅读 2 分钟次阅读

目录

基本介绍

计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。

算法过程

根据待排序集合中最大元素和最小元素的差值范围，申请额外空间；
遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；
对额外空间内数据进行计算，得出每一个元素的正确位置；
将待排序集合每一个元素移动到计算得出的正确位置上。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


    /**
     * 计数排序
     *
     * @param arr
     */
    public static void countSort(int[] arr) {
        // 找到最大值和最小值
        int max = arr[0], min = arr[0];
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        // 创建辅助空间，也就是创建一个辅助数组，用下标表示变换后的值，用值表示原始值出现的次数
        int[] countArr = new int[max - min + 1];
        for (int i : arr) {
            countArr[i - min]++;
        }
        // 还原
        int originalIndex = 0;
        for (int i = 0; i < countArr.length; i++) {
            for (int j = 0; j < countArr[i]; j++) {
                arr[originalIndex++] = i + min;
            }
        }
    }

算法分析

由算法示例可知，计数排序的时间复杂度为O(N+K)。因为算法过程中需要申请一个额外空间和一个与待排序集合大小相同的已排序空间，所以空间复杂度为 O(N+K)。由此可知，计数排序只适用于元素值较为集中的情况，若集合中存在最大最小元素值相差甚远的情况，则计数排序开销较大、性能较差。通过额外空间的作用方式可知，额外空间存储元素信息是通过计算元素与最小元素值的差值作为下标来完成的，若待排序集合中存在元素值为浮点数形式或其他形式，则需要对元素值或元素差值做变换，以保证所有差值都为一个非负整数形式。

参考

排序算法（八）：计数排序