常见排序算法原理——第三部分（桶排序、计数排序、基数排序）

引言

排序算法的前两篇文章，我们聊了冒泡、插入、选择、快排、归并、堆排序的六种排序算法。今天，我们来看三种时间复杂度为 O(n) 的排序算法：桶排序、计数排序、基数排序。因为他们的时间复杂度是线性的，所以也叫线性排序。

一、桶排序

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

时间复杂度分析

如果要排序的数据有 n 个，我们将其均匀的分到 m 个桶中，每个桶中分配到的元素就是 k=n/m 个。然后再对每个桶中的元素进行快速排序，时间复杂度就是O(klogk)。有 m 个桶，总共需要O(mklogk)。因为 k=n/m，所以时间复杂度就是O(nlogn/m)。当桶的个数接近数据的个数时，桶排序的复杂度接近O(n)。

使用场景

桶排序的使用场景很苛刻，首先待排序的数据需要很容易就能划分为 m 个桶，桶与桶之间天然有序。只有这样，每个桶内的数据在排完序后，桶之间不需要再排序。其次，数据要均匀的分布在各个桶内。极端情况下，数据都被分到一个桶里，时间复杂度退化为O(nlogn)。

桶排序使用在外部排序中。所谓外部排序就是数据保存在磁盘，不能将待排数据全部加载到内存进行排序。

二、计数排序

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

为什么要叫计数排序？“计数”从哪里来的呢？我们举个例子：现在有 8 名考生，满分 5 分，数组nums保存他们的考试成绩。考生的成绩从 0 ~ 5，我们使用score[6] 来表示桶。下标代表分数，对应的元素值表示对应分数的考生个数。

从图中可以看到，分数为3分的考生有3个，小于3分的有4个。所以，成绩为3分的考生在排序后的数组下标的位置是4，5，6。

那我们如何快速计算出，每个分数的考生在有序数组中对应的存储位置呢？思路很是巧妙：我们对scores数组进行顺序求和，如下：

接着，也是计数排序最核心的部分：我们遍历待排序数组nums，执行如下操作。比如，当扫描到 3 时，我们可以从数组 scores 中取出下标为 3 的值 7，也就是说，到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个，也就是说 3 是数组 Res 中的第 7 个元素（也就是数组 Res 中下标为 6 的位置）。当 3 放入到数组 Res 中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 scores[3]要减 1，变成 6。以此类推，当我们扫描到第 2 个分数为 3 的考生的时候，就会把它放入数组 Res 中的第 6 个元素的位置（也就是下标为 5 的位置）。

详细排序步骤参考下图：

这里接上图遍历到第四个元素0的情况。

最终，当我们扫描完整个数组 nums后，结果集数组 Res 中的数据就是按照分数从小到大有序排列的了。

三、基数排序

假设有10w条手机号，现在需要将其按从小到大进行排序，如何做呢？因为手机号位数比较多，桶排序和计数排序不适用。快速排序可以做到O(nlogn)，还能更快吗？

注意手机号有个特点，比如手机号a和b，a的前几位已经比b大的那么后面就可以不用比了。还记得之前订单排序的例子吗？没错，我们可以借助稳定排序的特性，先按照手机号的最后一位进行排序，倒数第二位，依次类推，直到第一位，这样所有的手机号就有序了。

手机号太长了，我们使用字符串来代替：

注意：每次排序都必须是稳定的排序算法，不能修改之前的相对大小的顺序。

根据每一位排序，我们可以使用桶排序或者计数排序做到时间复杂度O(n)。待排序的数据有k位，总的时间复杂度就是O（kn），当 k 远远小于n时，可以近似看做O(n)。

如果待排序的数据不是等长的，比如英文单词，有长有短。我们可以考虑在每个单词的后面拼接“0”，根据ASCII码，所有的字母都是大于“0”的，多以不会改变相对顺序。

小结：基数排序需要数据能分割出独立的位，而且位之间需要有递进关系，如果a的高位比b大，后面就不需要再比了。另外，每一位的范围不能太大，要能使用线性排序，否则时间复杂度做不到O(n)。

文章参考与<零声教育>的C/C++linux服务期高级架构系统教程学习: