软考软件设计师专题讲义九：数据结构相关算法

　　链式基数排序：

　　将关键码拆分为若干项，每项作为一个“关键码”，则对单关键码的排序可按多关键码排序方法进行。比如，关键码为4位的整数，可以每位对应一项，拆分成4项;又如，关键码由5个字符组成的字符串，可以每个字符作为一个关键码。由于这样拆分后，每个关键码都在相同的范围内(对数字是0～9，字符是'a'～'z')，称这样的关键码可能出现的符号个数为“基”，记作RADIX。上述取数字为关键码的“基”为10;取字符为关键码的“基”为26。基于这一特性，用LSD法排序较为方便。

　　基数排序：从最低位关键码起，按关键码的不同值将序列中的记录“分配”到RADIX个队列中，然后再“收集”之。如此重复d次即可。链式基数排序是用RADIX个链队列作为分配队列，关键码相同的记录存入同一个链队列中，收集则是将各链队列按关键码大小顺序链接起来。

　　【算法10.14】

　　#define MAX_KEY_NUM 8 /*关键码项数最大值*/

　　#define RADIX 10 /*关键码基数，此时为十进制整数的基数*/

　　#define MAX_SPACE 1000 /*分配的最大可利用存储空间*/

　　typedef struct{

　　KeyType keys[MAX_KEY_NUM]; /*关键码字段*/

　　InfoType otheritems; /*其它字段*/

　　int next; /*指针字段*/

　　}NodeType; /*表结点类型*/

　　typedef struct{

　　NodeType r[MAX_SPACE]; /*静态链表，r[0]为头结点*/

　　int keynum; /*关键码个数*/

　　int length; /*当前表中记录数*/

　　}L_TBL; /*链表类型*/

　　typedef int ArrayPtr[radix]; /*数组指针，分别指向各队列*/

　　void Distribute(NodeType *s，int i，ArrayPtr *f，ArrayPtr *e)

　　{ /*静态链表ltbl的r域中记录已按(kye[0]，keys[1]，…，keys[i-1])有序)*/

　　/*本算法按第i个关键码keys[i]建立RADIX个子表，使同一子表中的记录的keys[i]相同*/

　　/*f[0…RADIX-1]和e[0…RADIX-1]分别指向各子表的第一个和最后一个记录*/

　　for(j=0;j

　　for(p=r[0].next;p;p=r[p].next)

　　{ j=ord(r[p].keys[i]); /*ord将记录中第i个关键码映射到[0…RADIX-1]*/

　　if(!f[j]) f[j]=p;

　　else r[e[j]].next=p;

　　e[j]=p; /* 将p所指的结点插入到第j个子表中*/

　　}

　　}

　　void Collect(NodeType *r，int i，ArrayPtr f，ArrayPtr e)

　　{/*本算法按keys[i]自小到大地将f[0…RADIX-1]所指各子表依次链接成一个链表*e[0…RADIX-1]为各子表的尾指针*/

　　for(j=0;!f[j];j=succ(j)); /*找第一个非空子表，succ为求后继函数*/

　　r[0].next=f[j];t=e[j]; /*r[0].next指向第一个非空子表中第一个结点*/

　　while(j

　　{ for(j=succ(j);j

　　if(f[j]) {r[t].next=f[j];t=e[j];} /*链接两个非空子表*/

　　}

　　r[t].next=0; /*t指向最后一个非空子表中的最后一个结点*/

　　}

　　void RadixSort(L_TBL *ltbl)

　　{ /*对ltbl作基数排序，使其成为按关键码升序的静态链表，ltbl->r[0]为头结点*/

　　for(i=0;ilength;i++) ltbl->r[i].next=i+1;

　　ltbl->r[ltbl->length].next=0; /*将ltbl改为静态链表*/

　　for(i=0;ikeynum;i++) /*按最低位优先依次对各关键码进行分配和收集*/

　　{ Distribute(ltbl->r，i，f，e); /*第i趟分配*/

　　Collect(ltbl->r，i，f，e); /*第i趟收集*/

　　}

　　}

　　【效率分析】

　　时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。

　　空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总