排序算法：计数排序

前文说到，19591959 年 77 月，希尔排序通过交换非相邻元素，打破了O(n^2)的魔咒，使得排序算法的时间复杂度降到了O(nlogn) 级，此后的快速排序、堆排序都是基于这样的思想，所以他们的时间复杂度都是 O(nlogn)。

那么，排序算法最好的时间复杂度就是 O(nlogn) 吗？是否有比 O(nlogn) 级还要快的排序算法呢?能否在O(n^2)的时间复杂度下完成排序呢？

事实上，O(n) 级的排序算法存在已久，但他们只能用于特定的场景。

计数排序就是一种时间复杂度为 O(n) 的排序算法，该算法于 1954 年由 Harold H. Seward 提出。在对一定范围内的整数排序时，它的复杂度为 O(n+k)（其中 k 是整数的范围大小）。

伪计数排序

举个例子，我们需要对一列数组排序，这个数组中每个元素都是[1,9] 区间内的整数。那么我们可以构建一个长度为 9 的数组用于计数，计数数组的下标分别对应区间内的 9 个整数。然后遍历待排序的数组，将区间内每个整数出现的次数统计到计数数组中对应下标的位置。最后遍历计数数组，将每个元素输出，输出的次数就是对应位置记录的次数。

算法实现如下（以 [1,9]为例）：

public static void countingSort9(int[] arr) {
    // 建立长度为 9 的数组，下标 0~8 对应数字 1~9
    int[] counting = new int[9];
    // 遍历 arr 中的每个元素
    for (int element : arr) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置
        counting[element - 1]++;
    }
    int index = 0;
    // 遍历计数数组，将每个元素输出
    for (int i = 0; i < 9; i++) {
        // 输出的次数就是对应位置记录的次数
        while (counting[i] != 0) {
            arr[index++] = i + 1;
            counting[i]--;
        }
    }
}

算法非常简单，但这里的排序算法并不是真正的计数排序。因为现在的实现有一个非常大的弊端：排序完成后，arr 中记录的元素已经不再是最开始的那个元素了，他们只是值相等，但却不是同一个对象。

在纯数字排序中，这个弊端或许看起来无伤大雅，但在实际工作中，这样的排序算法几乎无法使用。因为被排序的对象往往都会携带其他的属性，但这份算法将被排序对象的其他属性都丢失了。

就好比业务部门要求我们将 1 号商品，2 号商品，3 号商品，4 号商品按照价格排序，它们的价格分别为 8 元、6 元，6 元，9 元。我们告诉业务部门：排序完成后价格为 6 元、 6 元、8 元，9元，但不知道这些价格对应哪个商品。这显然是不可接受的。

伪计数排序 2.0

对于这个问题，我们很容易想到一种解决方案：在统计元素出现的次数时，同时把真实的元素保存到列表中，输出时，从列表中取真实的元素。算法实现如下：

public static void countingSort9(int[] arr) {
    // 建立长度为 9 的数组，下标 0~8 对应数字 1~9
    int[] counting = new int[9];
    // 记录每个下标中包含的真实元素，使用队列可以保证排序的稳定性
    HashMap<Integer, Queue<Integer>> records = new HashMap<>();
    // 遍历 arr 中的每个元素
    for (int element : arr) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置
        counting[element - 1]++;
        if (!records.containsKey(element - 1)) {
            records.put(element - 1, new LinkedList<>());
        }
        records.get(element - 1).add(element);
    }
    int index = 0;
    // 遍历计数数组，将每个元素输出
    for (int i = 0; i < 9; i++) {
        // 输出的次数就是对应位置记录的次数
        while (counting[i] != 0) {
            // 输出记录的真实元素
            arr[index++] = records.get(i).remove();
            counting[i]--;
        }
    }
}

在这份代码中，我们通过队列来保存真实的元素，计数完成后，将队列中真实的元素赋到 arr 列表中，这就解决了信息丢失的问题，并且使用队列还可以保证排序算法的稳定性。

但是，这也不是真正的计数排序，计数排序中使用了一种更巧妙的方法解决这个问题。

真正的计数排序

举个例子，班上有 10 名同学：他们的考试成绩分别是：7,8,9,7,6,7,6,8,6,6，他们需要按照成绩从低到高坐到 0～9 共 10 个位置上。
用计数排序完成这一过程需要以下几步：

第一步仍然是计数，统计出：4 名同学考了 6 分，3 名同学考了 7 分，2 名同学考了 8 分，1 名同学考了 9 分；
然后从头遍历数组：第一名同学考了 77 分，共有 44 个人比他分数低，所以第一名同学坐在 44 号位置（也就是第 55 个位置）；
第二名同学考了 88 分，共有 77 个人（44 + 33）比他分数低，所以第二名同学坐在 77 号位置；
第三名同学考了 99 分，共有 99 个人（44 + 33 + 22）比他分数低，所以第三名同学坐在 99 号位置；
第四名同学考了 7 分，共有 4 个人比他分数低，并且之前已经有一名考了 7 分的同学坐在了 4 号位置，所以第四名同学坐在 5 号位置。
...依次完成整个排序。

区别就在于计数排序并不是把计数数组的下标直接作为结果输出，而是通过计数的结果，计算出每个元素在排序完成后的位置，然后将元素赋值到对应位置。

代码如下：

public static void countingSort9(int[] arr) {
    // 建立长度为 9 的数组，下标 0~8 对应数字 1~9
    int[] counting = new int[9];
    // 遍历 arr 中的每个元素
    for (int element : arr) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置
        counting[element - 1]++;
    }
    // 记录前面比自己小的数字的总数
    int preCounts = 0;
    for (int i = 0; i < counting.length; i++) {
        int temp = counting[i];
        // 将 counting 计算成当前数字在结果中的起始下标位置。位置 = 前面比自己小的数字的总数。
        counting[i] = preCounts;
        // 当前的数字比下一个数字小，累计到 preCounts 中
        preCounts += temp;
    }
    int[] result = new int[arr.length];
    for (int element : arr) {
        // counting[element - 1] 表示此元素在结果数组中的下标
        int index = counting[element - 1];
        result[index] = element;
        // 更新 counting[element - 1]，指向此元素的下一个下标
        counting[element - 1]++;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < arr.length; i++) {
        arr[i] = result[i];
    }
}

首先我们将每位元素出现的次数记录到 counting 数组中。

然后将 counting[i] 更新为数字 i 在最终排序结果中的起始下标位置。这个位置等于前面比自己小的数字的总数。

例如本例中，考 7 分的同学前面有 4 个比自己分数低的同学，所以 7 对应的下标为 4。

这一步除了使用 temp 变量这种写法以外，还可以通过多做一次减法省去 temp 变量：

// 记录前面比自己小的数字的总数
int preCounts = 0;
for (int i = 0; i < counting.length; i++) {
    // 当前的数字比下一个数字小，累计到 preCounts 中
    preCounts += counting[i];
    // 将 counting 计算成当前数字在结果中的起始下标位置。位置 = 前面比自己小的数字的总数。
    counting[i] = preCounts - counting[i];
}

接下来从头访问 arr 数组，根据 counting 中计算出的下标位置，将 arr 的每个元素直接放到最终位置上，然后更新 counting 中的下标位置。这一步中的 index 变量也是可以省略的。

最后将 result 数组赋值回 arr，完成排序。

这就是计数排序的思想，我们还剩下最后一步，那就是根据 arr 中的数字范围计算出计数数组的长度。使得计数排序不仅仅适用于
[1,9]，代码如下：

public static void countingSort(int[] arr) {
    // 判空及防止数组越界
    if (arr == null || arr.length <= 1) return;
    // 找到最大值，最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
        else if (arr[i] < min) min = arr[i];
    }
    // 确定计数范围
    int range = max - min + 1;
    // 建立长度为 range 的数组，下标 0~range-1 对应数字 min~max
    int[] counting = new int[range];
    // 遍历 arr 中的每个元素
    for (int element : arr) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置，这里需要将每个元素减去 min，才能映射到 0～range-1 范围内
        counting[element - min]++;
    }
    // 记录前面比自己小的数字的总数
    int preCounts = 0;
    for (int i = 0; i < range; i++) {
        // 当前的数字比下一个数字小，累计到 preCounts 中
        preCounts += counting[i];
        // 将 counting 计算成当前数字在结果中的起始下标位置。位置 = 前面比自己小的数字的总数。
        counting[i] = preCounts - counting[i];
    }
    int[] result = new int[arr.length];
    for (int element : arr) {
        // counting[element - min] 表示此元素在结果数组中的下标
        result[counting[element - min]] = element;
        // 更新 counting[element - min]，指向此元素的下一个下标
        counting[element - min]++;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < arr.length; i++) {
        arr[i] = result[i];
    }
}

这就是完整的计数排序算法。

倒序遍历的计数排序

计数排序还有一种写法，在计算元素在最终结果数组中的下标位置这一步，不是计算初始下标位置，而是计算最后一个下标位置。最后倒序遍历 arr 数组，逐个将 arr 中的元素放到最终位置上。

代码如下：

public static void countingSort(int[] arr) {
    // 防止数组越界
    if (arr == null || arr.length <= 1) return;
    // 找到最大值，最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
        else if (arr[i] < min) min = arr[i];
    }
    // 确定计数范围
    int range = max - min + 1;
    // 建立长度为 range 的数组，下标 0~range-1 对应数字 min~max
    int[] counting = new int[range];
    // 遍历 arr 中的每个元素
    for (int element : arr) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置，这里需要将每个元素减去 min，才能映射到 0～range-1 范围内
        counting[element - min]++;
    }
    // 每个元素在结果数组中的最后一个下标位置 = 前面比自己小的数字的总数 + 自己的数量 - 1。我们将 counting[0] 先减去 1，后续 counting 直接累加即可
    counting[0]--;
    for (int i = 1; i < range; i++) {
        // 将 counting 计算成当前数字在结果中的最后一个下标位置。位置 = 前面比自己小的数字的总数 + 自己的数量 - 1
        // 由于 counting[0] 已经减了 1，所以后续的减 1 可以省略。
        counting[i] += counting[i - 1];
    }
    int[] result = new int[arr.length];
    // 从后往前遍历数组，通过 counting 中记录的下标位置，将 arr 中的元素放到 result 数组中
    for (int i = arr.length - 1; i >= 0; i--) {
        // counting[arr[i] - min] 表示此元素在结果数组中的下标
        result[counting[arr[i] - min]] = arr[i];
        // 更新 counting[arr[i] - min]，指向此元素的前一个下标
        counting[arr[i] - min]--;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < arr.length; i++) {
        arr[i] = result[i];
    }
}

两种算法的核心思想是一致的，并且都是稳定的。第一种写法理解起来简单一些，第二种写法在性能上更好一些。

在计算下标位置时，不仅计算量更少，还省去了 preCounts 这个变量。在《算法导论》一书中，便是采用的此种写法。

实际上，这个算法最后不通过倒序遍历也能得到正确的排序结果，但这里只有通过倒序遍历的方式，才能保证计数排序的稳定性。

时间复杂度 & 空间复杂度

从计数排序的实现代码中，可以看到，每次遍历都是进行 n 次或者 k 次，所以计数排序的时间复杂度为 O(n+k)，k 表示数据的范围大小。

用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组，所以空间复杂度也是 O(n+k)。

需要注意的是，一般我们分析时间复杂度和空间复杂度时，常数项都是忽略不计的。但计数排序的常数项可能非常大，以至于我们无法忽略。不知你是否注意到计数排序的一个非常大的隐患，比如我们想要对这个数组排序：

int[] arr = new int[]{1, Integer.MAX_VALUE};

尽管它只包含两个元素，但数据范围是 [1,2^31]，我们知道 java 中 int 占 4 个字节，一个长度为 2^31次方的 int 数组大约会占 8G 的空间。如果使用计数排序，仅仅排序这两个元素，声明计数数组就会占用超大的内存，甚至导致 OutOfMemory 异常。

所以计数排序只适用于数据范围不大的场景。例如对考试成绩排序就非常适合计数排序，如果需要排序的数字中存在一位小数，可以将所有数字乘以 10，再去计算最终的下标位置。