线性排序

之前我们分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。这篇文章会介绍三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序，因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫做线性排序（Linear sort）。这三个算法是非基于比较的排序算法，不涉及元素之间的比较操作。

这几种排序算法理解起来不难，时间、空间复杂度分析起来也很简单，但是对要排序的数据要求很苛刻，所以这也是我们今天的学习重点，掌握这些排序算法的适用场景。

桶排序（Bucket sort）

首先，我们来看桶排序。桶排序，顾名思义，会用到 “桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

比如我们对这组金额在 0-50 之间的订单进行排序：

22，5，11，41，45，26，29，10，7，8，30，27，42，43，40。

桶排序的时间复杂度为什么是 O(n) ？我们一块儿来分析一下。

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

桶排序看起来很优秀，那它是不是可以替代我们之前讲的排序算法那？

答案当然是否定的。为了让你轻松理解桶排序的核心思想，刚才做了很多假设。实际上，桶排序对于要排序的数据要求是非常苛刻的。

首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

比如我们有 10 GB 的订单数据，我们希望按订单金额（假设订单金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次把 10 GB 的数据都加载到内存中。其实我们可以借助桶排序的处理思想来解决这个问题。

我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额华为到 100 个桶里，第一个桶存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶内对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02 … 99）。

理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀分到 100 个文件中，每个小文件中存储大约 100 MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件进行编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。

不过，你可能也发现，订单按照金额在 1 元和 10 万元之间并不一定是均匀分布的，所以 10 GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能是某个金额区间的数据特别多，划分之后对应的文件就会很大，没办法一次性读入内存。这又该怎么办？

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

计数排序（Counting sort）

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

比如按年龄排序可以把年龄划分为0-100个桶 遍历所有人将对应年龄的人放到对应的桶，再将各个桶拼接这个时候就完成排序了 和桶排序不同的是计数排序中桶存的不是元素而是元素的数量

我们都经历过高考，高考查分数系统你应该还记得。我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次？

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

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

想弄明白这个问题，我们就要来看计数排序算法的实现方法。还是拿考生那个例子解释，为了方便说明，这里对数据规模进行简化。假设只有 8 个考生，分数在 0 到 5 之间。这 8 个考生的成绩我们放到一个数组 A[8] 中，分别是 2，5，3，0，2，3，0，3。

考生的成绩从 0 分到 5 分，我们使用大小为 6 的数组 C[6] 表示桶，其中下标对应分数。不过 C[6] 内存储的并不是考生，而是对应的考生个数。像刚才举的例子，我们只需要遍历一遍考生分数，就可以得到 C[6] 的值。

那我们如何快速计算出，每个分数的考生在有序数组中对应的存储位置？这个处理方法非常巧妙，很不容易想到。

思路大概是这样：我们对 C[6] 数组顺序求和，C[6] 存储的数据就变成了下面这样子。C[K] 里存储小于等于分数 K 的考生个数。

有了前面的数据准备之后，下面就可以讲计数排序中最复杂、最难理解的一部分了。

我们从后到前依次扫描数组 A。比如，当扫描到 3 时，我们可以从数组 C 中取出下标为 3 的值 7，也就是说，到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个，也就是说 3 是数组 R 中的第 7 个元素（数组 R 中下标为 6 的位置）。当 3 放入数组 R 中后，小于等于 3 的元素就只剩下 6 个，所以相应的 C[3] 要减一，变成 6 。

以此类推，当我们扫描到第 2 个分数为 3 的考生的时候，就会把它放入数组 R 中的第 6 个元素的位置（下标为 5 的位置）。当我们扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列了。

上面的过程有点复杂，这里写成了代码，你可以对照看下。

function countingSort (arr, n) {
  if (n <= 1) return;

  let max = arr[0];

  for (let i = 1; i < n; i++) {
    if (max < arr[i]) {
      max = arr[i];
    }
  }

  const c = new Array(max + 1);

  for (let i = 0; i <= max; i++) {
    c[i] = 0;
  }

  for (let i = 0; i < n; i++) {
    c[arr[i]]++;
  }

  for (let i = 1; i <= max; i++) {
    c[i] = c[i - 1] + c[i];
  }

  const r = new Array(n);

  for (let i = n - 1; i >= 0; i--) {
    const idx = c[arr[i]] - 1;

    r[idx] = arr[i];
    c[arr[i]]--;
  }

  for (let i = 0; i < n; i++) {
    arr[i] = r[i];
  }
}

这里利用另外一个数组来计数的实现方式是不是很巧妙？这也是为什么这种排序算法叫计数排序的原因。不过，千万不能死记硬背，重要的是理解和会用。

总结一下，计数排序只能用在数据范围不大的场景中，如果数据范围 k 要比排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转换为非负整数。

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

基数排序（Radix sort）

我们再来看这样一个排序问题。假设我们有 10 万个手机号，希望将这 10 万个手机号从小到大排序，你有什么比较快速的排序方法？

我们之前讲的快排，时间复杂度可以做到 O(nlogn)，还有更高效的排序算法？桶排序、计数排序能派上用场嘛？手机号码有 11 位，范围太大，显然不适用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法？现在就来介绍一种新的排序算法，基数排序。

刚刚这个问题里有这样的规律：假设要比较两个手机号 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大，那后面的几位就不用看了。

借助稳定排序算法，这里有一个巧妙的思路。还记得之前说排序算法稳定性时，举的订单的例子嘛？我们这里也可以借助相同的处理思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后。手机号码就都有序了。

注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序完全就没有意义了。

根据每一位来排序，我们可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k * n)。当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。

实际上，有时候排序的数据并不是等长的，比如我们排序牛津字典中的 20 万个英文单词，最短的只有 1 个字母，最长的有 45 个字母。对于这种不等长的值，基础排序还适用嘛？

Pneumonoultramicroscopicsilicovolcanoconiosis 矽肺病，肺尘病，硅酸盐沉着病

实际上，我们可以把所有单词补齐到相同长度，位数不够的可以在后面补 “0”，因为根据 ASCII 值，所有字母都大于 “0”，所以补 “0” 不会影响原有的大小顺序，这样就可以继续用基数排序。

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

总结

今天学习了 3 种线性时间复杂度的排序算法，有桶排序、计数排序、基数排序。它们对要排序的数据都有比较苛刻的要求，应用不是非常广泛。但是如果数据特征比较符合这些排序算法的要求，应用这些，算法，会非常高效，线性时间复杂度可以达到 O(n)。

桶排序和计数排序的排序思想是非常相似的，都是针对范围不大的数据，将数据划分为不同的桶来实现排序。基数排序要求数据可以划分为高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一位的范围不能太大，因为基数排序算法要借助桶排序或者计数排序来完成每一个位的排序工作。

技术拓展

如何根据年龄给 100 万用户排序？

实际上，根据年龄给 100 万用户排序，就类似于按照成绩给 50 万考生排序。我们假设年龄的范围最小是 1 岁，最大不能超过 120 岁。我们可以遍历这 100 万用户，根据年龄将其划分到这 120 个桶里，然后依次顺序遍历这 120 个桶内的元素。这样就得到了按照年龄排序的 100 万数据。

字符串排序（D，a，F，B，c，A，Z）

如果我们需要对 D，a，F，B，c，A，Z 这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序之后为 a，c，z，D，F，B，A，这个如何实现？如果字符串存储的不仅有大小写字母，还有数字。要将小写字母的放到最前面，大写字母放到后面，数字放到中间，不用排序算法，又该怎么解决？

。。。