上两节中，我带你着重分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。今天，我会讲三种时间复杂度是 的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。
按照惯例，我先给你出一道思考题：如何根据年龄给 100 万用户排序？ 你可能会说，我用上一节课讲的归并、快排就可以搞定啊！是的，它们也可以完成功能，但是时间复杂度最低也是 O(nlogn)。有没有更快的排序方法呢？让我们一起进入今天的内容！
桶排序（Bucket sort）
首先，我们来看桶排序。桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
桶排序的时间复杂度为什么是 呢？我们一块儿来分析一下。
如果要排序的数据有 n 个，尽量做到将它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。我们会基于某种映射函数f ，将待排序列的元素 映射到[1, m]范围类的第i个桶中，下标则为[0, m - 1]。
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。若每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 。
为了使桶排序更加高效，我们需要做到这两点：
1、在额外空间充足的情况下，尽量增大桶的数量；
2、使用的映射函数能够将输入的 n 个数据均匀的分配到 m 个桶中；
桶排序看起来很优秀，那它是不是可以替代我们之前讲的排序算法呢？
答案当然是否定的。为了让你轻松理解桶排序的核心思想，我刚才做了很多假设。实际上，桶排序对要排序数据的要求是非常苛刻的。
首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 的排序算法了。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？
现在我来讲一下，如何借助桶排序的处理思想来解决这个问题。
我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02...99）。
理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
不过，你可能也发现了，订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ，所以 10GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢？
针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元....901 元到 1000 元。如果划分之后，101 元到 200 元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。
桶排序动态图
我的总结
关于桶排序的思考
关于先定义桶的数量还是先定义桶的容量的问题，这个还是根据数据的有序性。
对于数值的问题，我的一种思路是可以先定义桶的数量
int bucketCount = 数组元素个数开方 + 1
然后元素映射通下标函数用到的 key
int key = (max - min) / bucketCount + 1;
每个桶预设容量
int bucketSize = key / 2 + 1;
元素映射到第 result 个桶的算法
int bucketIndex = (arr[i] - min) / key;
当然这里面有很多动态的地方。如何优化桶大小和数量，根据数组中元素设计合理的元素映射通下标函数，对于同一个桶的排序算法选取+对于数据结构（数组还是链表）都用很多考究的地方。
计数排序（Counting sort）
我个人觉得，计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
计数排序中最复杂、最难理解的一部分就是从后到前依次扫描数组并经过处理放置到临时数组的过程。此后临时数组内的数据就是按照分数从小到大有序排列的了。
计数排序-动图
代码示例
// arr 是 int 数组
public static void sort(int[] arr) {
if (arr.length <= 1) {
return;
}
// 找出最小值 和 最大值, 确定数据的范围
int min = arr[0];
int max = min;
int i, j, k;
for (i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
// 定义计数数组 c 数组，数组长度为 max - min + 1, 区间范围为[min, max]
int length = max - min + 1;
int[] c = new int[length];
// 填充 c 数组
for (i = 0; i < arr.length; i++) {
// 元素放置到对应下标的桶
c[value2Index(arr[i], min)]++;
}
// c 会累加各项目的值
for (i = 1; i < c.length; i++) {
c[i] += c[i - 1];
}
// 创建临时数组newArr，存储排序之后的结果
int[] newArr = new int[arr.length];
for (i = arr.length - 1; i >= 0; i--) {
// 根据数值找到对应的 c 下标对应的位置
j = arr[i];
k = value2Index(j, min);
// 取出下标
c[k]--;
// 赋值到 newArr
newArr[c[k]] = j;
}
// newArr 取代 arr
for (i = arr.length - 1; i >= 0; i--) {
arr[i] = newArr[i];
}
}
// 元素放置在所在下标的桶里
private static int value2Index(int value, int min) {
return value - min;
}
我总结一下，计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
基数排序（Radix sort）
我们再来看这样一个排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
我们之前讲的快排，时间复杂度可以做到 O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢？现在我就来介绍一种新的排序算法，基数排序。
刚刚这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。借助稳定排序算法，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。手机号码稍微有点长，画图比较不容易看清楚，我用字符串排序的例子，画了一张基数排序的过程分解图，你可以看下。
实际上，有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的 20 万个英文单词，最短的只有 1 个字母，最长的我特意去查了下，有 45 个字母，中文翻译是尘肺病。对于这种不等长的数据，基数排序还适用吗？实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。
我来总结一下，基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
内容小结
今天，我们学习了 3 种线性时间复杂度的排序算法，有桶排序、计数排序、基数排序。它们对要排序的数据都有比较苛刻的要求，应用不是非常广泛。但是如果数据特征比较符合这些排序算法的要求，应用这些算法，会非常高效，线性时间复杂度可以达到 O(n)。
桶排序和计数排序的排序思想是非常相似的，都是针对范围不大的数据，将数据划分成不同的桶来实现排序。基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作。
我的代码实现
https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s6/sort3
参考
13 | 线性排序：如何根据年龄给100万用户数据排序？ https://time.geekbang.org/column/article/42038
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
【算法】排序算法之桶排序 - 知乎 https://zhuanlan.zhihu.com/p/125737294
java/13_sorts · 编程语言算法集/algo - 码云 - 开源中国 https://gitee.com/TheAlgorithms/algo/tree/master/java/13_sorts
网友评论