鏈式基數排序：

　　將關鍵碼拆分為若干項，每項作為一個“關鍵碼”，則對單關鍵碼的排序可按多關鍵碼排序方法進行。比如，關鍵碼為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個指針。

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總