前言

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

那么，排序算法最好的时间复杂度就是 O(nlogn)吗？

事实上，存在 O(n)级的排序算法，但只能用于特定的场景。
计数排序(Counting Sort)，就是一种时间复杂度为 O(n)的排序算法，该算法于 1954年由 Harold H.Seward 提出。
在对一定范围内的整数排序时，它的复杂度为 Ο(n+k)（其中 k 是整数的范围大小）。

排序思路

这种排序算法不是基于比较元素大小的，而是利用数组下标来确定元素的正确位置。
例如，需要对一列数组排序，这个数组中每个元素都是[0, 10]区间内的整数，如果是基于元素比较的排序，就需要比较整数大小进行调整位置。

1. 我们可以根据这个数组的取值范围，构建一个长度为 11 的数组用于计数，计数数组的下标分别对应区间内的 11 个整数。
2. 然后遍历待排序的数组，将区间内每个整数出现的次数统计到计数数组中对应下标的位置。
3. 最后遍历计数数组，将每个元素输出，输出的次数就是对应位置记录的次数。

对应的代码实现

public static int[] countSort(int[] array) {
    // 1.得到数列的最大值
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }

    // 2.根据数列最大值确定统计数组的长度：有个缺点
    int[] countArray = new int[max + 1];

    // 3.遍历数列，填充统计数组
    for (int i = 0; i < array.length; i++) {
        countArray[array[i]]++;
    }

    //4.遍历统计数组，输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for (int i = 0; i < countArray.length; i++) {
        for (int j = 0; j < countArray[i]; j++) {
            sortedArray[index++] = i;
        }
    }
    return sortedArray;
}

改进

虽然这种思路非常简单，但这样的排序算法并不是真正的计数排序。

改进1

以待排序数列的最大值 + 1 作为统计数组的长度，并不严谨，可能会造成空间浪费。
例如，输入的数列中最大值为 1000，但是最小值为 990；如果新建一个长度为 1001 的统计数组，那么从 0 到 989 的空间都没用上。
所以，使用数列中元素大小的极值差（最大值 - 最小值） + 1 作为统计数组的长度。
同时，数列的最小值作为一个偏移量，用于统计数组的对号入座，也就是说，元素A对应的统计数组下标是 A - min(min 为最小值)。

public static int[] countSort2(int[] array) {
    // 1.得到数列的最大值与最小值
    int max = array[0], min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min){
            min = array[i];
        }
    }

    // 2.根据数列的取值范围确定统计数组的长度：避免浪费空间
    int[] countArray = new int[max - min + 1];

    // 3.遍历数列，填充统计数组
    for (int i = 0; i < array.length; i++) {
        // 偏移量等于数列的最小值
        countArray[array[i] - min]++;
    }

    //4.遍历统计数组，输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for (int i = 0; i < countArray.length; i++) {
        for (int j = 0; j < countArray[i]; j++) {
            sortedArray[index++] = i;
        }
    }
    return sortedArray;
}

该进2

还有一个非常大的弊端：排序完成后，数组中记录的元素已经不再是最开始的那个元素了，它们只是数值相等，但却不是同一个对象。
所以，如果是单纯的纯数字排序，这种做法没问题，但在实际工作中，这样的排序算法几乎无法使用。
因为被排序的对象往往都会携带其他的属性，但这份算法将被排序对象的其他属性都丢失了。
例如，老师对学生们的考试成绩排序，只知道排序的结果，不知道分数对应的学生姓名（如果分数是唯一的还能知道，分数相同的就不知道了）。

这种情况，可以使用哈希表来解决，但这也不是真正的计数排序。

真正的计数排序

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

public static void countSort3(int[] array) {
    // 判空及防止数组越界
    if (array == null || array.length <= 1) {
        return;
    }

    // 找到最大值，最小值
    int max = array[0];
    int min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        } else if (array[i] < min) {
            min = array[i];
        }
    }
    // 确定计数范围：元素极值 + 1
    int range = max - min + 1;
    // 建立长度为 range 的数组，下标 0~range-1 对应数字 min~max
    int[] counting = new int[range];
    // 遍历 arr 中的每个元素
    for (int element : array) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置
        // 这里需要将每个元素减去 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[array.length];
    for (int element : array) {
        // counting[element - min] 表示此元素在结果数组中的下标
        result[counting[element - min]] = element;
        // 更新 counting[element - min]，指向此元素的下一个下标
        counting[element - min]++;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < array.length; i++) {
        array[i] = result[i];
    }
}

倒序遍历的计数排序

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

public static void countSort4(int[] array) {
    // 防止数组越界
    if (array == null || array.length <= 1) {
        return;
    }
    // 找到最大值，最小值
    int max = array[0];
    int min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        } else if (array[i] < min) {
            min = array[i];
        }
    }
    // 确定计数范围
    int range = max - min + 1;
    // 建立长度为 range 的数组，下标 0~range-1 对应数字 min~max
    int[] counting = new int[range];
    // 遍历 arr 中的每个元素
    for (int element : array) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置，
        // 这里需要将每个元素减去 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[array.length];
    // 从后往前遍历数组，通过 counting 中记录的下标位置，将 arr 中的元素放到 result 数组中
    for (int i = array.length - 1; i >= 0; i--) {
        // counting[arr[i] - min] 表示此元素在结果数组中的下标
        result[counting[array[i] - min]] = array[i];
        // 更新 counting[arr[i] - min]，指向此元素的前一个下标
        counting[array[i] - min]--;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < array.length; i++) {
        array[i] = result[i];
    }
}

两种算法的核心思想是一致的，并且都是稳定的。第一种写法理解起来简单一些，第二种写法在性能上更好一些。
在计算下标位置时，不仅计算量更少，还省去了 preCounts 这个变量。在《算法导论》一书中，便是采用的此种写法。
实际上，这个算法最后不通过倒序遍历也能得到正确的排序结果，但这里只有通过倒序遍历的方式，才能保证计数排序的稳定性。

动画演示

演示动画来自于Visualgo

复杂度分析

从计数排序的实现代码中，可以看到，每次遍历都是进行 n 次或者 k 次，所以计数排序的时间复杂度为 O(n + k)，k 表示数据的范围大小，快于任何比较排序算法。
用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组，所以空间复杂度也是 O(n + k)。
需要注意的是，一般我们分析时间复杂度和空间复杂度时，常数项都是忽略不计的。
但计数排序的常数项可能非常大，以至于我们无法忽略。

计数排序存在一个非常大的隐患，比如我们想要对这个数组排序：

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

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

所以，计数排序只适用于数据范围不大且数据分布比较密集的场景。
此外，当数列元素不是整数，也不适用计数排序。

参考

程序员小灰
百度百科
LeetCode