前面我们分析了几种常用的排序算法的原理、时间复杂度、空间复杂度、稳定性等。下面我们讲三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。之所以能做到 O(n) 的时间复杂度，主要原因是这三个算法都不是基于比较的排序算法，都不涉及元素之间的比较操作，因此对要排序的数据要求很苛刻，只有在特定情况下才能使用该算法。

桶排序

桶排序（Bucket sort）的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
image.png

1. 代码实现

  1. public static int[] sort(int[] array, int bucketSize) {
  2.     if (array == null || array.length < 2) {
  3.             return;
  4.     }
  5.     // 获取最大值、最小值
  6.     int max = array[0];
  7.     int min = array[0];
  8.     for (int i = 1; i < array.length; i++) {
  9.         if (array[i] > max) {
  10.             max = array[i];
  11.         }
  12.         if (array[i] < min) {
  13.             min = array[i];
  14.         }
  15.     }
  16.     // 根据最大值最小值求桶数量
  17.     int bucketCount = (max - min) / bucketSize + 1;
  18.     int[][] buckets = new int[bucketCount][bucketSize];
  19.     // 记录每个桶的元素数量
  20.     int[] index = new int[bucketCount];
  21.     // 循环数组填充到桶里
  22.     for (int i = 0; i < array.length; i++) {
  23.         int bucketIndex = (array[i] - min) / bucketSize;
  24.         // 桶满了进行扩容
  25.         if (index[bucketIndex] == buckets[bucketIndex].length) {
  26.             int[] temp = buckets[bucketIndex];
  27.             int[] newBucket = new int[temp.length * 2];
  28.             System.arraycopy(temp, 0, newBucket, 0, temp.length);
  29.             buckets[bucketIndex] = newBucket;
  30.         }
  31.         // 放到指定桶里的数组的后面
  32.         buckets[bucketIndex][index[bucketIndex]++] = array[i];
  33.     }
  34.     // 循环对桶内元素进行快排，并把桶内元素依次赋值到原数组
  35.     int k = 0;
  36.     for (int i = 0; i < buckets.length; i++) {
  37.         if (index[i] == 0) {
  38.             continue;
  39.         }
  40.         QuickSort.sort(buckets[i]);
  41.         for (int j = 0; j < index[i]; j++) {
  42.             array[k++] = buckets[i][j];
  43.         }
  44.     }
  45.     return array;
  46. }

从时间复杂度的角度来看，核心逻辑只有：每个桶通过快排进行排序，最后循环取出每个桶中的元素。如果当桶的个数接近元素个数时，时间复杂度接近O(n)。前面的取最大值、最小值、分桶操作都是前置条件。

2. 场景分析

桶排序的时间复杂度为什么是 O(n) ？
如果对 n 个数据排序，先把它们均匀地划分到 m 个桶内，每个桶里有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k logk)。m 个桶排序的时间复杂度就是 O(mk logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶个数 m 接近数据个数 n 时，log(n/m) 就是非常小的常量，此时桶排序的时间复杂度接近 O(n)。

桶排序的局限性？
实际上，桶排序对要排序数据的要求是非常苛刻的。首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

桶排序的使用场景？
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）排序，但我们的内存只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。此时我们就可以借助桶排序的处理思想来解决这个问题。

我们可以先扫描一遍文件，看订单金额所处的数据范围。假设订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，每一个桶对应一个文件并且按照金额范围的大小顺序编号命名。理想的情况下，如果订单金额是均匀分布的，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。

如果订单金额不是均匀分布的 ，划分之后对应的文件还是没法一次性读入内存。此时我们可以针对这些划分之后还是比较大的文件继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间。如果划分之后，还是无法一次性读入内存，那就继续划分，直到所有的文件都能读入内存为止。

计数排序

计数排序（Counting sort）其实是桶排序的一种特殊情况，只是桶的大小粒度不一样。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，这样就省掉了桶内排序的时间。

比如我们要对 50 万考生的成绩进行排序得出名次，假设满分是 100 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 101 个桶，对应分数从 0 分到 100 分。根据考生的成绩将它们划分到这 101 个桶里。桶内的数据是相同的所以不需要再进行排序。我们只需要依次扫描每个桶，再将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

1. 算法思想

计数排序的算法思想就是这么简单，跟桶排序非常类似，只是桶的大小粒度不一样。不过，为什么这个排序算法叫“计数”排序呢？“计数”的含义来自哪里呢？

以考生的例子来解释。假设有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8] 中，它们分别是：2，5，3，0，2，3，0，3。然后用数组 C[6] 表示桶，其中下标对应分数。不过，C[6] 内存储的并不是考生，而是对应的考生个数。我们只需要遍历一遍考生分数，就可以得到 C[6] 的值。

从图中可以看到，分数为 3 分的考生有 3 个，小于 3 分的考生有 4 个，所以成绩为 3 分的考生在排序之后的有序数组 R[8] 中，会保存下标 4，5，6 的位置。
image.png
那我们如何快速计算出，每个分数的考生在有序数组中对应的存储位置呢？思路是这样的：我们对 C[6] 数组顺序求和，C[6]存储的数据就变成了下面这样子。C[k] 里存储小于等于分数 k 的考生个数。

假设有两个考生考了 0 分，两个考生考了 2 分，三个考生考了 3 分，一个考生考了 5 分。我们对 C[6] 数组顺序求和，C[6] 存储的数据就变成了下面这样子。C[k] 里存储小于等于分数 k 的考生个数。
image.png
我们从后到前依次扫描数组 A。当扫描到第一个元素 3 时，我们可以从数组 C 中取出下标为 3 的值是 7，即到目前为止包括自己在内，分数小于等于 3 的考生有 7 个，因此 3 是数组 R 中的第 7 个元素（即下标为 6 的位置）。当 3 放入到数组 R 中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 C[3] 要减 1，变成 6。

以此类推，当我们扫描到第 2 个分数为 3 的考生时，就会把它放入数组 R 中的第 6 个元素的位置（即下标为 5 的位置）。当我们扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的了。
image.png
计数排序适用场景：
总结一下，计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

比如，现在要将考生成绩精确到小数后一位，我们就需要将所有的分数都先乘以 10，转化成整数后再放到 101 个桶内。再比如，如果要排序的数据中有负数，数据的范围是 [-1000, 1000]，那我们就需要先对每个数据都加 1000，转化成非负整数。

动画演示：
countingSort.gif

2. 代码实现

public static void sort(int[] array) {
    if (array == null || array.length < 2) {
        return;
    }
    // 获取最大值做为桶的数量。因为桶必须从0开始，所以不需要最小值
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    // 记录每个桶的元素数量,下标大小[0,max]
    int[] count = new int[max + 1];
    // 计算每个元素的个数
    for (int i = 0; i < array.length; i++) {
        count[array[i]]++;
    }
    // 依次累加
    for (int i = 1; i < max + 1; i++) {
        count[i] = count[i-1] + count[i];
    }
    int[] tmp = new int[array.length];
    for (int i = array.length - 1; i >= 0; i--) {
        // array[i]为分数，count[array[i]]为小于等于这个分数的数量
        int index = count[array[i]] - 1;
        tmp[index] = array[i];
        // 小于等于这个分数的数量减1
        count[array[i]]--;
    }
    // 将结果拷贝回array数组
    System.arraycopy(tmp, 0, array, 0, array.length);
}

基数排序

假设我们现在要对 10 万个手机号进行从小到大排序，该使用哪种排序算法呢？虽然快排的时间复杂度可以做到 O(nlogn)，但还有更高效的排序算法吗？由于手机号码有 11 位，范围太大，显然也不适合用桶排序、计数排序这两种排序算法。针对这个问题，我们可以通过基数排序（Radix sort）以 O(n) 的时间复杂度排序。

1. 算法思想

刚刚这个问题里有这样的规律：假设要比较两个手机号 a、b 的大小，如果在前面几位中 a 已经比 b 大了，那后面的几位就不用看了。借助稳定排序算法，我们先按最后一位来排序手机号，然后再按倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。下图用字符串排序的例子描述了一下基数排序的过程分解。
image.png
注意，这里按照每位来排序的排序算法要是稳定的，因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，而不会去管其他位的大小关系，那么低位的排序就没有意义了。

动画演示：
radixSort.gif

2. 代码实现

public static void radixSort(int[] array) {
    // 只考虑正数
    int maxDigit = getMaxDigit(array);
    radixSort(array, maxDigit);
}

/**
 * 获取最高位数
 */
private static int getMaxDigit(int[] array) {
    // 找到最大值
    int max = array[0];
    for (int value : array) {
        if (max < value) {
            max = value;
        }
    }
    // 获取最大值的位数
    int maxLen = 0;
    for (long temp = max; temp != 0; temp /= 10) {
        maxLen++;
    }
    return maxLen;
}

private static void radixSort(int[] array, int maxDigit) {
    int mod = 10;
    int dev = 1;
    // 遍历比较数组元素的每一位
    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        int[][] counter = new int[10][0];
        for (int item : array) {
            // 取待比较的位上的数字
            int bucket = ((item % mod) / dev);
            // 落到对应的桶
            counter[bucket] = arrayAppend(counter[bucket], item);
        }
        // 按排序结果进行组织
        int index = 0;
        for (int[] bucket : counter) {
            for (int value : bucket) {
                array[index++] = value;
            }
        }
    }
}

/**
 * 自动扩容，并保存数据
 */
private static int[] arrayAppend(int[] array, int value) {
    array = Arrays.copyOf(array, array.length + 1);
    array[array.length - 1] = value;
    return array;
}

时间复杂度分析
根据每一位来排序，我们可以用桶排序或计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或计数排序，总的时间复杂度是 O(kn)。当 k 不大的时，基数排序的时间复杂度就近似于 *O(n)。

基数排序的使用场景？
实际上，有时候要排序的数据并不都是等长的，比如英文单词，最短的只有 1 个字母，最长的有 45 个字母。对于这种不等长的数据，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据 ASCII 值，所有字母都大于 0，所以补 0 不会影响到原有的大小顺序。这样就可以继续用基数排序了。

总结一下，基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，且位之间有递进的关系，如果 a 的高位比 b 大，那剩下的低位就不用比较了。此外每一位的数据范围不能太大，要可以用线性排序算法来排序，否则基数排序的时间复杂度就无法做到 O(n) 了。