Java 十大排序算法之计数排序刨析

算法介绍

计数排序是一个时间复杂度为O(n+k)的非基于比较的排序算法，其中n是待排序元素的个数，k是待排序元素的范围，即待排序元素的最大值减去最小值再加1。

算法通过构建一个长度为k的计数数组来统计每个元素出现的次数，然后借助计数数组按顺序输出每个元素，就完成了排序过程。

因为计数排序是非基于比较的算法，因此可以在一定程度上提高排序效率。不过需要注意的是，计数排序只适用于元素范围不大的场景，如果范围过大，统计计数数组可能会占用大量内存，导致性能下降。

算法过程

1. 统计待排序元素的出现次数，构建一个长度为k的计数数组countArr，遍历待排序数组，将每个元素出现的次数记录在计数数组中；

2. 计算元素在有序序列中的位置，根据countArr统计出每个元素的前缀和，即sumArr。sumArr[i]表示小于等于i的元素个数；

3. 将元素按照sumArr的顺序依次放到有序序列sortedArr中，具体操作如下：

4. 遍历待排序数组，取元素arr[i]；

5. 查找元素arr[i]在计数数组中的出现次数count，即count=countArr[arr[i]]；
6. 将元素arr[i]插入到sortedArr中的位置sumArr[arr[i]]-1，同时将countArr[arr[i]]-1；
7. 重复以上过程，直到待排序数组arr中的所有元素都被放到sortedArr中。

代码实现

public static void countSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    int min = arr[0], max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    int[] countArr = new int[max - min + 1];
    // 统计出现次数
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i] - min]++;
    }
    // 计算前缀和
    for (int i = 1; i < countArr.length; i++) {
        countArr[i] += countArr[i - 1];
    }
    int[] sortedArr = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        int pos = countArr[arr[i] - min] - 1;
        sortedArr[pos] = arr[i];
        countArr[arr[i] - min]--;
    }
    System.arraycopy(sortedArr, 0, arr, 0, arr.length);
}

示例说明

示例1

int[] arr = {5, 3, 8, 4, 2, 5, 7, 1, 9, 6};
countSort(arr);
Arrays.toString(arr); // [1, 2, 3, 4, 5, 5, 6, 7, 8, 9]

在该示例中，待排序数组arr中的元素最小值为1，最大值为9，因此计数数组countArr的长度为9，记录每个元素出现的次数后，计算前缀和sumArr，然后根据sumArr将元素依次放到sortedArr中。

示例2

int[] arr = {4, 2, 4, 4, 3, 8, 3, 1, 5, 7};
countSort(arr);
Arrays.toString(arr); // [1, 2, 3, 3, 4, 4, 4, 5, 7, 8]

在该示例中，待排序数组arr中的元素最小值为1，最大值为8，因此计数数组countArr的长度为8，记录每个元素出现的次数后，计算前缀和sumArr，然后根据sumArr将元素依次放到sortedArr中。