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语言代码:
领取专属 10元无门槛券
私享最新 技术干货