数据结构浙江大学整理（3）

10.3 基数排序

10.3.1 桶排序

举例：假设我们有N个学生，他们的成绩是0到100之间的整数（于是有于是有M=101个不同的成绩值个不同的成绩值）。如何在线性时间内将学生按成绩排序？

我们可以为每一个成绩值构造一个“桶”，于是就有了101个桶，如图1所示。如果我们有一个88分的学生，那么就把学生的信息查到88分的这个链表的表头里，伪码描述如下：

时间复杂度：T(N,M)=O(M+N)

插入学生的成绩，因为是N个学生，所以复杂度为O(N)；输出成绩，for循环，M个成绩，自然复杂度为O(M)。故总的时间复杂度如上。

如果有N=40000个学生，由于M=101，故这就是一个线性的复杂度。

图1

但是，如果M>>N怎么办？

10.3.2 基数排序

举例：假设我们有N=10个整数，每个整数的值在0到999之间之间（于是有于是有M=1000个不同的值个不同的值）。还有可能在线性时间内排序吗？

这里的基数就是跟进制有关，如果是二进制，基数就是2；如果是十进制，基数就是10。这里我们说的是十进制，所以基数就是10。

加入我们的输入序列为：64,8,216,512,27,729,0,1,343,125，用“次位优先”（Least Significant Digit，LSD）算法。主位是指的第一位，剩余的都叫次位。因此这里比较我们先从个位开始。

首先我们建立十个“桶”，然后将它们以个位数为标准放到这10个桶里面去，如表中Pass 1；然后按照十位数为标准放到10个桶里，如Pass 2；在完成之后，我们来做一个收集，收集的过程就是扫描每一个桶，然后把桶里的元素按照0,1,8,512,216……顺序用一个链表把它们串起来；串起来后，按照主位放到相应的桶里，如Pass3；最后，再对它们进行一次收集，用链表连起来，得出结果。

表3.1 基数排序算法流程表

时间复杂度：T(N,B,P)=O(P(N+B))。其中P为基数排序次数（本例子例为3），N为输入序列中数字个数，B为整数进制。

10.3.3 多关键字排序

例如，一副扑克牌是按2种关键字排序的，如图2所示，花色是它的主关键字，面值是它的次关键字。

图2

在这里，我们可以用“主位优先”（Most Significant Digit, MSD）排序，为花色建立4个桶，在每个桶里分别排序，最后合并结果。

也可以使用“次位优先”（LSD）算法排序，为面值建立13个桶，就可以直接将结果合并，然后为花色建4个桶，放进去就可以了。

在这里，LSD优点是不需要排序，时间复杂度小的多。

基数排序是稳定的算法。

补充

（1）次位优先的C语言代码：

（2）主位优先C语言代码：