10.6.2 基数排序的两种实现方法

　　实现基数排序可以有两种不同算法。

　一、链式基数排序

　　类似于表插入排序，附设指针数组将顺序表视作一个"静态链表"，利用"修改指针"实现分配和收集。同时设置rd个队列的头指针和尾指针，分别指示各队列的"头结点"和"尾结点"在链表中的位置。

　　首先初始化空队列，即将每个队列的头指针 front[i] 和尾指针 rear[i] 均设为 "0"；"分配" 时将记录"插入"队列，若队列为空，则仅需修改队列的头、尾指针，令它们指向该插入记录，否则在修改队列的尾指针的同时尚需修改当前队尾记录的指针； "收集"时依次头尾相接地链接各非空队列所指记录，即改变各非空队列尾指针所指记录的指针，令它们指向"下一"非空队列头指针所指记录，最后一个非空队列尾指针所指记录的指针应为"空"。

算法 算法 10.18
　　void LRadixSort(SqList &L)
　{
　　// 附设指针数组，对L作链式基数排序，并最后将它调整为有序序列
　　int Next[L.length+1];
　　for (i=0; i<L.length; ++i) Next[i] = i+1;
　　Next[L.length] = 0;　　　　　　　　// 将L视作静态(循环)链表
　　for ( k=L.bitsnum-1; k>=0; --k) {
　　　　　　　　　　　　　// 按最低位优先依次对各关键字进行分配和收集
　　　Distribute(L.r, k, f, e, Next);　// 第 k 趟分配
　　　Collect(L.r, k, f, e, Next); 　　// 第 k 趟收集
　　}// for
　　Arrange(L, Next); 　　　　　　　　// 按 Next[] 的值调整 L 中的记录
　} // LRadixSort
　
算法 算法 10.19
　　void Distribute (RcdType R[], int k, int f[], int e[])
　{
　// R 中记录已按(R.keys[k+1],...,R.keys[L.bitsnum-1]) 有序，
　// 本算法按 R.keys[k] 建立 RADIX 个子表，使同一子表中记录的
　// keys[k] 相同。f[0..RADIX-1] 和 e[0..RADIX-1] 分别指向各子
　// 表中第一个和最后一个记录
　　for (j=0; j<Radix; ++j) f[j] = 0; 　// 各子表初始化为空表
　　for (p=Next[0]; p; p=Next[p]) {
　　　j = ord(R[p].keys[k]);
　　　　　　　　　　　// ord 将记录中的关键字keys[k]映射到[0..RADIX-1]中
　　　if ( !f[j] ) f[j] = p;
　　　else Next[e[j]] = p;
　　　e[j] = p; 　　　　　　　　　　　// 将 p 所指的结点插入相应子表
　　}// for
　} // Distribute
　
算法 算法 10.20
　　void Collect (RcdType R[], int k, int f, int e)
　{
　　// 本算法按 R.keys[k] 自小至大地将 f[0..RADIX-1] 所指各子表
　　// 依次链接成一个链表，e[0..RADIX-1] 为各子表的尾指针
　　for ( j=0; !f[j]; j=succ(j));// 找第一个非空子表，succ 为求后继函数
　　　Next[0] = f[j]; t = e[j];
　　　　　　　　　　　　　　　　 // Next[0]指向第一个非空子表中第一个结点
　　while ( j<RADIX ) {
　　　for (j=succ(j); j<RADIX-1 && !f[j]; j=succ(j) );// 找下一个非空子表
　　　if ( f[j] ) { r[t].next = f[j]; t = e[j]; } // 链接两个非空子表
　　}// while
　　Next[t] = 0;　　　　　　　　// t 指向最后一个非空子表中的最后一个结点
　} // Collect

　　链式基数排序的时间复杂度为O (d(n+rd))，或简写为O (dn)。		  

　　链式基数排序的过程如动画所示。动画

　　显然，这不是最后的排序结果，和表插入类似，尚需利用函数 Arrange 将表中记录调整为按关键字有序排列。

　　在描述基数排序的算法之前，尚需重新定义记录和顺序表类型：

　const MAX_NUM_OF_KEY = 8;
　　　　　// 关键字项数的最大值，暂定为8
　const RADIX = 10;
　　　　　// 关键字基数，此为十进制整数的基数
　typedef struct {
　　KeysType keys[MAX_NUM_OF_KEY]; // 关键字
　　InfoType otheritems; // 其它数据项
　} RcdType; // 基数排序中的记录类型
　typedef struct {
　　RcdType r[MAXSIZE+1];
　　int length; 　// 顺序表长度
　　int bitsnum;　// 关键字位数
　} SqList;　　　 // 顺序表类型


　　分析链式基数排序的时间复杂度：假设 n 为记录个数，rd 为基数值，d 为构成逻辑关键字的关键字位数。由于每一趟的"分配"都是对全部记录处理一遍，因此它的时间复杂度是O (n)，而每一趟的"收集"只是巡查一遍队列，依次将各非空队列的队尾指针所指结点链接到下一个非空队列的队头指针所指结点，因此它的时间复杂度是O (rd)，因此一趟分配和收集的时间复杂度为O (n+rd)，对每一位关键字进行一趟分配和收集，因此总的时间复杂度为
O (d(n+rd))，一般情况下，相比 n 而言，rd 要小得多，因此可简写为O (dn)。换句话说，当待排序序列中的记录数量很大，而逻辑关键字的"位数"较小，此时用基数排序法进行排序将比快速排序的效率更高。