軟考軟件設(shè)計師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　鏈?zhǔn)交鶖?shù)排序：

　　將關(guān)鍵碼拆分為若干項，每項作為一個“關(guān)鍵碼”，則對單關(guān)鍵碼的排序可按多關(guān)鍵碼排序方法進行。比如，關(guān)鍵碼為4位的整數(shù)，可以每位對應(yīng)一項，拆分成4項;又如，關(guān)鍵碼由5個字符組成的字符串，可以每個字符作為一個關(guān)鍵碼。由于這樣拆分后，每個關(guān)鍵碼都在相同的范圍內(nèi)(對數(shù)字是0～9，字符是'a'～'z')，稱這樣的關(guān)鍵碼可能出現(xiàn)的符號個數(shù)為“基”，記作RADIX。上述取數(shù)字為關(guān)鍵碼的“基”為10;取字符為關(guān)鍵碼的“基”為26�；�于這一特性，用LSD法排序較為方便。

　　基數(shù)排序：從最低位關(guān)鍵碼起，按關(guān)鍵碼的不同值將序列中的記錄“分配”到RADIX個隊列中，然后再“收集”之。如此重復(fù)d次即可。鏈?zhǔn)交鶖?shù)排序是用RADIX個鏈隊列作為分配隊列，關(guān)鍵碼相同的記錄存入同一個鏈隊列中，收集則是將各鏈隊列按關(guān)鍵碼大小順序鏈接起來。

　　【算法10.14】

　　#define MAX_KEY_NUM 8 /*關(guān)鍵碼項數(shù)最大值*/

　　#define RADIX 10 /*關(guān)鍵碼基數(shù)，此時為十進制整數(shù)的基數(shù)*/

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

　　typedef struct{

　　KeyType keys[MAX_KEY_NUM]; /*關(guān)鍵碼字段*/

　　InfoType otheritems; /*其它字段*/

　　int next; /*指針字段*/

　　}NodeType; /*表結(jié)點類型*/

　　typedef struct{

　　NodeType r[MAX_SPACE]; /*靜態(tài)鏈表，r[0]為頭結(jié)點*/

　　int keynum; /*關(guān)鍵碼個數(shù)*/

　　int length; /*當(dāng)前表中記錄數(shù)*/

　　}L_TBL; /*鏈表類型*/

　　typedef int ArrayPtr[radix]; /*數(shù)組指針，分別指向各隊列*/

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

　　{ /*靜態(tài)鏈表ltbl的r域中記錄已按(kye[0]，keys[1]，…，keys[i-1])有序)*/

　　/*本算法按第i個關(guān)鍵碼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個關(guān)鍵碼映射到[0…RADIX-1]*/

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

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

　　e[j]=p; /* 將p所指的結(jié)點插入到第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為求后繼函數(shù)*/

　　r[0].next=f[j];t=e[j]; /*r[0].next指向第一個非空子表中第一個結(jié)點*/

　　while(j

　　{ for(j=succ(j);j

　　if(f[j]) {r[t].next=f[j];t=e[j];} /*鏈接兩個非空子表*/

　　}

　　r[t].next=0; /*t指向最后一個非空子表中的最后一個結(jié)點*/

　　}

　　void RadixSort(L_TBL *ltbl)

　　{ /*對ltbl作基數(shù)排序，使其成為按關(guān)鍵碼升序的靜態(tài)鏈表，ltbl->r[0]為頭結(jié)點*/

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

　　ltbl->r[ltbl->length].next=0; /*將ltbl改為靜態(tài)鏈表*/

　　for(i=0;ikeynum;i++) /*按最低位優(yōu)先依次對各關(guān)鍵碼進行分配和收集*/

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

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

　　}

　　}

　　【效率分析】

　　時間效率：設(shè)待排序列為n個記錄，d個關(guān)鍵碼，關(guān)鍵碼的取值范圍為radix，則進行鏈?zhǔn)交鶖?shù)排序的時間復(fù)雜度為O(d(n+radix))，其中，一趟分配時間復(fù)雜度為O(n)，一趟收集時間復(fù)雜度為O(radix)，共進行d趟分配和收集。

　　空間效率：需要2*radix個指向隊列的輔助空間，以及用于靜態(tài)鏈表的n個指針。

　　　　　　　計算機軟考軟件設(shè)計師練習(xí)試題及答案解析匯總