1.算法介绍

基数排序的思想是“多关键字排序”，前面已经讲过了。基数排序有两种实现方式：第一种叫作最高位优先，即先按最高位排成若干子序列，再对每个子序列按次高位排序。举扑克牌的例子，就是先按花色排成4个子序列，再对每种花色的13张牌进行排序，最终使所有扑克牌整体有序。第二种叫作最低位优先，这种方式不必分成子序列，每次排序全体关键字都参与。最低位可以优先这样进行，不通过比较，而是通过“分配”和“收集”。还是扑克牌的例子，可以先按数字将牌分配到13个桶中，然后从第一个桶开始依次收集；再将收集好的牌按花色分配到4个桶中，然后还是从第一个桶开始依次收集。经过两次“分配”和“收集”操作，最终使牌有序。

2.执行流程

下面通过一个例子来体会基数排序过程，初始桶如图8-5所示。

图8-5 初始桶

原始序列：278 109 063 930 589 184 505 269 008 083

每个关键字的每一位都是由“数字”组成的，数字的范围是0～9，所以准备10个桶用来放关键字。要注意的是，组成关键字的每一位不一定是数字。例如，如果关键字的某一位是扑克牌的花色，因为花色有4种，所以在按花色那一位排序时，要准备4个桶。同理，如果关键字有一位是英文字母，那么按这一位排序时，就要准备26个桶（假设不区分大小写）。这里所说的“桶”，其实是一个先进先出的队列（从桶的上面进，下面出）。

1）进行第一趟分配和收集，要按照最后一位。

① 分配过程如下（注意，关键字从桶的上面进入）：

278的最低位是8，放到桶8中，如图8-6所示。

图8-6 278放桶8中

109的最低位是9，放到桶9中，如图8-7所示。

图8-7 109放桶9中

按照这样的方法，依次（按原始序列顺序）将原始序列的每个数放到对应的桶中。第一趟分配过程完成，结果如图8-8所示。

图8-8 第一趟结果

② 收集过程是这样的：按桶0到桶9的顺序收集，注意关键字从桶的下面出。

桶0：930

桶1：没关键字，不收集

桶2：没关键字，不收集

桶3：063，083

桶8：278，008

桶9：109，589，269

将每桶收集的关键字依次排开，所以第一趟收集后的结果为：

930 063 083 184 505 278 008 109 589 269

注意观察，最低位有序了，这就是第一趟基数排序后的结果。

2）在第一趟排序结果的基础上，进行第二趟分配和收集，这次按照中间位。

①第二趟分配过程如下：

930的中间位是3，放到桶3中，如图8-9所示。

图8-9 930放桶3中

063的中间位是6，放到桶6中，如图8-10所示。

图8-10 063放桶6中

按照同样的方法，将其余关键字依次入桶，结果如图8-11所示。

图8-11 第二趟结果

②进行第二趟收集。(www.daowen.com)

桶0：505，008，109

桶1：没关键字，不收集

桶2：没关键字，不收集

桶3：930

桶8：083，184，589

桶9：没关键字，不收集

第二趟收集结果为：

505 008 109 930 063 269 278 083 184 589

此时中间位有序了，并且中间位相同的那些关键字，其最低位也是有序的，第二趟基数排序结束。

3）在第二趟排序结果的基础上，进行第三趟分配和收集，这次按照最高位。

①第三趟分配过程如下：

505的最高位是5，放到桶5中，如图8-12所示。

图8-12 505放桶5中

008的最高位是0，放到桶0中，如图8-13所示。

图8-13 008放桶0中

按照同样的方法，将其余关键字依次入桶，结果如图8-14所示。

图8-14 第三趟结果

②进行第三趟收集。

桶0：008，063，083

桶1：109，184

桶2：269，278

桶3：没关键字，不收集

桶8：没关键字，不收集

桶9：930

第三趟收集结果为：

008 063 083 109 184 269 278 505 589 930

现在最高位有序，最高位相同的关键字按中间位有序，中间位相同的关键字按最低位有序（这里没体现出来），于是整个序列有序，基数排序过程结束。

3.性能分析

时间复杂度：平均和最坏情况下都是O（d（n+r_d））。

空间复杂度：O（r_d）。

其中，n为序列中的关键字数；d为关键字的关键字位数，如930，由3位组成，d=3；r_d为关键字基的个数，这里的基指的是构成关键字的符号，如关键字为数值时，构成关键字的符号就是0～9这些数字，一共有十个，即r_d=10。

这里简单讲解基数排序时间复杂度的记忆方法。基数排序每一趟都要进行“分配”和“收集”。“分配”需要依次对序列中的每个关键字进行，即需要顺序扫描整个序列，所以有n这一项；“收集”需要依次对每个桶进行，而桶的数量取决于关键字的取值范围，如放数字的桶有10个，放花色的桶有4个等，刚好是r_d的值，所以有r_d这一项，因此一趟“分配”和“收集”需要的时间为n+r_d。整个排序需要多少趟的“分配”和“收集”呢？需要d趟，即关键字的关键字位数有几位，就需要几趟。例如上面的例子，关键字由3位组成，所以要进行3趟。

因此，时间复杂度为O（d（n+r_d））。

至于空间复杂度，因为每个桶实际上是一个队列，需要头尾指针，共有r_d个桶，所以需要2r_d个存放指针的空间，因此是O（r_d）。

说明：基数排序适合的场景是序列中的关键字数很多，但组成关键字的关键字的取值范围较小，如数字0～9是可以接受的。如果关键字的取值范围也很大，如26个字母，并且序列中大多数关键字的最高位关键字都不相同，那么这时可以考虑使用“最高位优先法”，先根据最高位排成若干子序列，然后分别对这些子序列进行直接插入排序。