9.8　基数排序

前面所述各类排序方法都是按照关键字大小进行的一种排序方法,而基数排序不同。基数排序是一种借助于多关键字排序的思想对单逻辑关键字进行排序的方法,即先将关键字分解成若干部分,然后通过对各部分关键字的分别排序,最终完成对全部记录的排序。

基数排序首先把每个关键字看作为一个d元组:K_i＝（K_i⁰,K_i¹,…,K_i^d－1）。其中,C₀≤K_i^j≤C_r－1（1≤i≤n,0≤j≤d－1）,r称为基数。设置r个桶,排序时先按K_i^d－1从大到小将记录分配到r个桶中,然后依次收集这些记录,称之为一趟基数排序。再按K_i^d－2从大到小将记录分配到r个桶中,如此反复,直到对K_i⁰分配和收集,最终得到的便是排好序的序列。基数r的选择和关键字的分解法因关键字的类型而异。关键字为十进制整数时,r＝10,C₀＝0,C_r－1＝9,关键字的每一位取值范围为0≤K_i^j≤9,d为关键字的最大位数。关键字为二进制数时,r＝2,C₀＝0,C_r－1＝1,关键字的每一位取值为0或1,d为关键字的最大位数。关键字为字母串时,r＝26,C₀＝‘A’,C_r－1＝‘Z’,关键字的每一位取值范围为‘A’≤K_i^j≤‘Z’,d为关键字中字母的最大长度。

基数排序是一种最低位优先法。它先按最低位K_i^d－1将序列中的n个记录“分配”到C₀至C_r－1个子序列中,再将序列按顺序“收集”起来成为一个序列,从而完成第1趟排序；第2趟排序按次低位K_i^d－2将序列中的n个记录“分配”到C₀到C_r－1个序列中,再按顺序将子序列“收集”起来,如此循环,直到最后一趟,按K₀“分配”和“收集”完成之后,基数排序结束。

【例9－7】　用基数排序的方法进行排序,初始序列为:L→362→745→885→957→054→786→080→543→012→565。

首先,将表中记录按个位数分配到编号为从0到9的10个子链表中。

[0]→080　　　　　　　　　　[5]→745→885→565

[1]→　　　　　　　　　　　 [6]→786

[2]→362→012　　　　　　　 [7]→957

[3]→543　　　　　　　　　　[8]→

[4]→054　　　　　　　　　　[9]→

然后,将上面10个链表收集起来,成为如下链表（所谓收集,就是将10个链表依次链接起来）。

L→080→362→012→543→054→745→885→565→786→957

再次将表中记录按十位数分配到编号为从0到9的10个子链表中。

[0]→　　　　　　　　　　　[5]→054→957

[1]→012　　　　　　　　 　[6]→362→565

[2]→　　　　　　　　　　　[7]→

[3]→　　　　　　　　　　　[8]→080→885→786

[4]→543→745　　　　　　　[9]→

然后,将上面10个链表收集起来,成为如下链表。

L→012→543→745→054→957→362→565→080→885→786

最后,再将表中记录按百位数分配到编号为从0到9的10个子链表中。

[0]→012→054→080　　　　 [5]→543→565

[1]→　　　　　　　　　　　[6]→

[2]→　　　　　　　　　　　[7]→745→786

[3]→362　　　　　　　　　 [8]→885

[4]→　　　　　　　　　　　[9]→957

然后,将上面10个链表收集起来,成为如下链表。至此,基数排序结束。

L→012→054→080→362→543→565→745→786→885→957

在基数排序中,反复使用了“分配”和“收集”这两种基本操作来实现排序。为实现基数排序,假定关键字是由d个分量组成的组合关键字,每个分量具有T类型,类型T的基数为RD,故而需要一个由RD个链表构成的存储结构,每个链表设立一个表头指针f和一个表尾指针e,这样需要两个长度均为RD的指针数组。

具体算法描述如下。

分配算法描述如下。

【算法分析】

假设有n个待排序记录,每个记录含d个关键字,每个关键字取值范围为rd。

（1）每一趟分配的时间复杂度为O（n）,每一趟收集的时间复杂度为O（RD）,又因整个排序需要进行d趟分配和收集,所以链式基数排序的时间复杂度为O（d（n＋RD））。

（2）在排序的时候,需要RD个队列的头指针和尾指针,故算法所需要的辅助空间为2RD个。另外,采用链表结构较顺序结构而言还增加了n个指针域空间。

（3）基数排序是稳定的。基数排序只适用于字符串和整数这类有明显结构特征的关键字,并且适用于n较大、d较小的场合。