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

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

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

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

　　【算法10.14】

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

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

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

　　typedef struct{

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

　　InfoType otheritems; /*其它字段*/

　　int next; /*指針字段*/

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

　　typedef struct{

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

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

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

　　}L_TBL; /*鏈表類型*/

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

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

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

　　/*本算法按第i個(gè)關(guān)鍵碼keys[i]建立RADIX個(gè)子表，使同一子表中的記錄的keys[i]相同*/

　　/*f[0…RADIX-1]和e[0…RADIX-1]分別指向各子表的第一個(gè)和最后一個(gè)記錄*/

　　for(j=0;j

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

　　{ j=ord(r[p].keys[i]); /*ord將記錄中第i個(gè)關(guān)鍵碼映射到[0…RADIX-1]*/

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

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

　　e[j]=p; /* 將p所指的結(jié)點(diǎn)插入到第j個(gè)子表中*/

　　}

　　}

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

　　{/*本算法按keys[i]自小到大地將f[0…RADIX-1]所指各子表依次鏈接成一個(gè)鏈表*e[0…RADIX-1]為各子表的尾指針*/

　　for(j=0;!f[j];j=succ(j)); /*找第一個(gè)非空子表，succ為求后繼函數(shù)*/

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

　　while(j

　　{ for(j=succ(j);j

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

　　}

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

　　}

　　void RadixSort(L_TBL *ltbl)

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

　　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)先依次對(duì)各關(guān)鍵碼進(jìn)行分配和收集*/

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

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

　　}

　　}

　　【效率分析】

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

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

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