桶排序、计数排序和基数排序 #

这三种排序的时间复杂度都是线性的，为 O(n)，所以这类算法叫作 线性排序。之所以能做到线性的时间复杂度，主要原因是它们并非是基于比较的排序算法。

桶排序（Bucket sort） #

桶排序的核心思想 #

桶排序核心思想就是：将要排序的数据分到几个有序的桶里，每个桶里的数据单独进行排序。桶内排完序之后，再依次将它们里的数据取出，就可以组成有序的序列了。

时间复杂度 #

有 n 个数据，把它们均匀的分到 m 个桶里，每个桶有 k = n/m 个数据。然后每个桶内的数据都使用归并排序（使用快排则不是稳定排序）进行排序，每个桶内的排序时间复杂度为 O(k * logk)，那么总的时间复杂度就是 O(m * k * logk)，把 k = n/m 代入就得到 O(nlogn/m)。当 m 接近 n 时，这个时候桶排序的数据复杂度就接近 O(n)。

使用要求 #

1. 首先要排序的数据要很容易的划分成 m 个同桶，并且桶与桶之间有着天然的大小关系，这样每个桶内的数据排好序之后，桶与桶之间的数据不需要排序。
2. 数据在各个桶之间的分布要比较均匀。在极端情况下，都划分到一个桶里，那么时间复杂度就退化为 O(nlogn) 了。

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

例如，我们有 10GB 的订单数据，想按照订单金额（假设都是正整数）进行排序，但是内存有限，只有几百 MB，没办法将 10GB 的数据都加载到内存中。怎么做？

用桶排序的思想来解决这个问题。

首先，我们需要知道金额范围，这样才能划分桶。需要遍历扫描一遍数据，假设扫描之后知道金额最小是 1 元，最大是 10 万元。接着根据订单金额划分成 100 个桶，第一个桶 1~1000，第二个桶 1000~2000，...，依次类推。每个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02，...，99）。

理想情况下，订单金额均匀分布，所以被均匀的划分到 100 个文件，每个文件大小为 100 M。

然后我们就可以依次地将这 100 个小文件放到内存中，用快排来进行排序。等所有文件都排好序之后，只需要按照文件编号，从小到大依次读取每个小文件的中的订单数据，并将其写入到一个文件中，那么这个文件中存储的就是按照金额从小到大排序的订单数据了。

不过，实际中订单金额在 1 元到 10 万元之间可能不是均匀分布的，所以可能某个区间的数据特别多，划分之后对应的文件也就很大，没法一次性读入内存。那又该怎么办？

针对这些划分之后依然很大的文件，处理方式和前面是一样的，对它继续划分。比如 1 元到 1000 元的订单比较多，那么就将这个区间继续划分为 10 个小区间：1~100，100~200，...，900~1000。这样之后如果某个区间还是过大，无法读入内存，比如 1~100 区间还是过大，那就对它继续划分，直到所有文件都可以读入内存。

计数排序（Counting sort） #

技术排序可以看作是桶排序的一种特殊情况。

计数排序的核心思想 #

计数排序的核心思想就是，当要排序 n 个数据的时候，所处的范围并不大，比如最大值是 k，我们就可以把数据划分到 k 个桶，每个桶内的数据都是相同的，节省了桶内排序的时间。

使用要求 #

计数排序只能用在数据范围不大的情况，如果数据范围 k 比要排序的数据量 n 大很多，那就不适合计数排序了。而且计数排序只能给非负整数排序，如果要排序的数据是其他类型，要将其在不改变先对大小的情况下，转化为非负整数。例如，考生成绩精确到小数点以为，我们可以将所有分数都乘以 10，化成整数。

记得高考查分数吗？查分数的时候会显示我们的成绩还有排名。加入所在省份有 50 万考生，如何通过成绩快速排序得出名次呢？

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

基数排序 #

假设现在有 10 万个手机号，希望将它们从小到大排序，有什么比较快的排序方法呢？

通过快排，时间复杂度可以做到 O(nlogn)，还有更高效的吗？桶排序、计数排序不太合适，手机号码有 11 位，范围太大。那有没有时间复杂度是 O(n) 的算法呢？看一下基数排序是怎么做的。

刚刚问题，我们需要注意到：假设比较两个手机号码 a、b 的大小，如果前面几位中，a 已经比 b 大，那后面的就不用看了。

借助稳定的排序，这里有一个巧妙的设计思路：先按照最后 1 位来排序，然后再按照倒数第 2 位排序，依次类推，最后按照第 1 位进行排序。经过 11 次排序之后，手机号码就都是有序的了。

注意每一位的排序算法都要是稳定的，否则就不正确了。如果是非稳定的算法，那么当前位的排序只考虑自己的大小，完全不管其他位大小，这样，那么低位的排序就没有意义了。

每一位的排序都可以通过桶排序或者计数排序来实现，它们的时间复杂度是 O(n)，排序的数据有 k 位，那么时间复杂度就是 O(k*n)，k 不 大的时候，比如手机号码为 11 位，这个时候时间复杂度就接近于 O(n)。

使用要求 #

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