计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

1.排序过程

  • 找出待排序的数组中最大和最小的元素；
  • 创建一个桶（数组），大小是最大值-最小值+1。
  • 遍历待排序数组，并往相应的桶里计数
  • 遍历桶，找出计数大于0的下标，重新填入待排序数组

2.代码实现(Java)

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
public static void countingSort(int[] arr) {
    if (arr.length == 0) return;
    int min = arr[0], max = arr[0];
    // 查找最大最小值
    for (int i = 1; i < arr.length; i++) {
        if (min > arr[i])
            min = arr[i];
        if (max < arr[i])
            max = arr[i];
    }
    // 设置桶的大小
    int[] bucket = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        // 计数，在当前值减去最小值的位置
        bucket[arr[i] - min]++;
    }
    int index = 0;
    for (int i = 0; i < bucket.length; i++) {
        if (bucket[i] > 0) {
            // 桶的下标加上最小值就是原来的值
            arr[index] = i + min;
            index++;
            // 当前桶的计数 -1
            bucket[i--]--;
        }
    }
}

3.算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

但是他的缺点也很明显，就是无法对小数进行排序。同时如果数据较大的话在空间和时间上不优于其他排序算法。所以在实际项目中要斟酌考虑。