计数排序

计数排序是一种非基于比较的排序算法，我们之前介绍的各种排序算法几乎都是基于元素之间的比较来进行排序的，计数排序的时间复杂度为 O(n + m )，m 指的是数据量，说的简单点，计数排序算法的时间复杂度约等于 O(n)，快于任何比较型的排序算法

代码实现

public static void sort(int[] arr) {
    //找出数组中的最大值
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    //初始化计数数组
    int[] countArr = new int[max + 1];

    //计数
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i]]++;
        arr[i] = 0;
    }

    //排序
    int index = 0;
    for (int i = 0; i < countArr.length; i++) {
        if (countArr[i] > 0) {
            arr[index++] = i;
        }
    }
}

计数局限性

计数排序的毛病很多，我们来找找 bug 。

如果我要排的数据里有 0 呢？ int[] 初始化内容全是 0 ，排毛线。

如果我要排的数据范围比较大呢？比如[ 1，9999 ]，我排两个数你要创建一个 int[10000] 的数组来计数？

对于第一个 bug ，我们可以使用偏移量来解决，比如我要排[ -1，0，-3 ]这组数字，这个简单，我全给你们加 10 来计数，变成[ 9，10，7 ]计完数后写回原数组时再减 10。不过有可能也会踩到坑，万一你数组里恰好有一个 -10，你加上 10 后又变 0 了，排毛线。

对于第二个 bug ，确实解决不了，如果是[ 9998，9999 ]这种虽然值大但是相差范围不大的数据我们也可以使用偏移量解决，比如这两个数据，我减掉 9997 后只需要申请一个 int[3] 的数组就可以进行计数。

由此可见，计数排序只适用于正整数并且取值范围相差不大的数组排序使用，它的排序的速度是非常可观的。