概述

简单来说, 计数排序就是申请一个相同数据范围的数组空间, 计算每个数字各有几个,如此即可.

如一个数组为: [5, 2, 3, 4, 6, 3, 1, 0]

申请一个长度为6的数组(因为数组范围为0-5), 其中的值为: [1, 1, 1, 2, 1, 1, 1]

其数组意思就是, 0有1个,1有1个, 类推

最后将其拼装为排序好的数组即可

通过描述可以看出, 这个排序不适合范围过大的数组, 如果有一个长度为2的数组: [1, 9999999999999], 虽然数组很短, 但是用计数排序的话, 计数数组也是十分大的. 而对于数字范围小, 且重复数字很多的情况, 那就很好了.

其时间空间复杂度如下:

Java代码实现

好吧, 计数排序很简单, 简单Java代码实现:

/**
 * 计数排序, 从小到大顺序
 * @param arr
 */
public static void countSort(int[] arr) {
    if(arr.length < 1) {
        return;
    }
    // 数组中的最小和最大值, 用于确定数组范围
    int min = arr[0], max = arr[0];
    // 查找数组中的最大和最小值
    for(int i = 1; i < arr.length; i++) {
        // 更新最小值
        if(arr[i] < min) {
            min = arr[i];
        }
        // 更新最大值
        if(arr[i] > max) {
            max = arr[i];
        }
    }
    // 用于计数的数组, 长度为数组的范围, 值为该数字的个数
    int[] tmp = new int[max - min + 1];
    // 对数组进行计数, 将计数数组相应位置加一
    for(int i = 0; i < arr.length; i++) {
        tmp[arr[i] - min]++;
    }
    // 计数完成后,将其更新回原数组即可
    int index = 0;
    // 遍历计数数组
    for(int i = 0; i < tmp.length; i++) {
        // 当前数组有几个就写回几个
        for(int j = 0; j < tmp[i]; j++) {
            arr[index] = i + min;
            index++;
        }
    }
}