【正文】 6. 已知序列 {27， 35， 11， 9， 18， 30， 3， 23， 35，20}，請(qǐng)給出采用歸并排序法對(duì)該序列作遞增排序時(shí)的每一趟的結(jié)果。 ?解 :依題義單鏈表定義如下 : struct node { int key。 p=r[p].next。 基數(shù)排序算法 void radixsort (rsqlist r, int d, int n,int p) { /*d為關(guān)鍵字的位數(shù) ， n為待排序的數(shù)據(jù)個(gè)數(shù) ， p指向鏈表中的第一個(gè)結(jié)點(diǎn) */ int i,j,t?；鶖?shù)排序是采用“分散”的辦法排序。amp。 /* 初始建堆 */ for (i=n。這個(gè)調(diào)整過程稱為“ 篩選 ”。 Quicksort(r, low, k1)。 x=r[i]。 } r[k+d]=r[0]。 ?簡(jiǎn)單選擇排序是不穩(wěn)定的排序算法。如某趟掃描后 flag仍為 1，說明此趟掃描已無數(shù)據(jù)互換，則排序結(jié)束，不必再繼續(xù)掃描了。 for (i=1。設(shè)前 I1個(gè)記錄已經(jīng)有序，從第 I個(gè)記錄開始和前 I1個(gè)記錄的關(guān)鍵字比較，找到合適的位置插入。 記錄的形式定義為： Typedef struct rectype { KeyType key。 /*記錄后移 */ j。 for( j=1。 i++) { k=i。 for (i=d+1, i=n。 圖 快速排序 [ 13 15 7 10 30 4 8 25 ] [ 8 4 7 10] 13 [ 30 15 25 ] [ 7 4 ] 8 [ 10] 13 [ 30 15 25 ] 4 7 8 10 13 [ 30 15 25 ] 4 7 8 10 13 [ 25 15] 30 4 7 8 10 13 15 25 30 ?一趟快速排序采用從兩頭向中間掃描的辦法。 if (ij) /*已找到了滿足 r[i].keyx的 r[i] { r[j]=r[i]。 返回 堆排序 ?堆的概念 ?堆排序（ Heap Sort）是利用二叉樹的一種排序方法。 /*x不大于左右兒子 ， 即已找到 } /*了合適的位置 i， 循環(huán)結(jié)束 r[i]=x。 ?兩個(gè)有序表的歸并稱為二路歸并。 else { k=(s+t)/2。然后將原始數(shù)據(jù)隊(duì)列中各結(jié)點(diǎn)，按所考慮的關(guān)鍵字某位數(shù)的值插入到相應(yīng)“盒”的隊(duì)列中去。 i) /*從關(guān)鍵字的最后一位開始 */ { for (j=0。 /*收尾 */ } } 圖 初始狀態(tài) ?現(xiàn)以圖 306， 028，009， 948， 505， 917， 721， 430， 390為例說明 radixsort函數(shù)的執(zhí)行過程。 } temp=pkey。 返回 。 q=pnext。 t=e[j]。 /*原始數(shù)據(jù)串成靜態(tài)鏈表，頭指針為 p*/ 基數(shù)排序算法續(xù) for ( i=d。 圖 基數(shù)排序 3 0 6 0 2 8 0 0 9 9 4 8 5 0 5 9 1 7 7 2 1 4 3 0 3 9 0 ( a ) 原始數(shù)據(jù) key 390 430 721 505 306 917 948 028 009 盒 0 1 2 3 4 5 6 7 8 9 4 3 0 3 9 0 7 2 1 5 0 5 3 0 6 9 1 7 0 2 8 9 4 8 0 0 9 ( b ) 第一趟 key 009 306 505 917 028 721 430 948 390 盒 0 1 2 3 4 5 6 7 8 9 5 0 5 3 0 6 0 0 9 9 1 7 7 2 1 0 2 8 4 3 0 9 4 8 3 9 0 ( c ) 第二趟 key 028 009 390 306 430 505 721 948 917 盒 0 1 2 3 4 5 6 7 8 9 0 0 9 0 2 8 3 0 6 3 9 0 4 3 0 5 0 5 7 2 1 9 1 7 9 4 8 ( d ) 第三趟 ?為每個(gè)“盒”設(shè)置一個(gè)鏈接隊(duì)列，并將各隊(duì)列的隊(duì)首和隊(duì)尾指針分別存于兩個(gè)一維數(shù)組中。 ?二路歸并的遞歸算法如下： 二路歸并排序函數(shù) void mergesort (r[], r1[], s, t) /*將 r[s..t]中的記 { int k。 ?堆排序是不穩(wěn)定的。 /*左右兒子中較小者上移 ， i=j。 ?快速排序更偏愛一個(gè)“ 雜亂無章 ”的序列。amp。依此遞歸地做下去，直至每個(gè)小部分中的數(shù)據(jù)個(gè)數(shù)為 1時(shí)，排序過程就結(jié)束了。 i++) shellpass(r[], n, dk[i])。 for (i=1。 in。 /* r[0]用于暫時(shí)存放待插入的元素 */ j= i1。這個(gè)作為排序依據(jù)的字段稱之為關(guān)鍵字。如果數(shù)據(jù)恰好應(yīng)插入到序列的最后端，則不需移動(dòng)數(shù)據(jù)，可節(jié)省時(shí)間，所以若原始數(shù)據(jù)大體有序，此算法可以有較快的運(yùn)算速度。 i++) { for ( j=1。 基本思想： ?第一趟從 R[0]— R[n1]中最小的記錄，并 R[1]交換；第二趟從 R[2]— R[n]選擇最小的 J記錄并與 R[2]交換；依次進(jìn)行下去，進(jìn)行了 (n1)趟掃描以后就完成了整個(gè)排序過程。 ?簡(jiǎn)單選擇 1. 輸入是已知的； 2. 每一趟排序結(jié)束后，所選擇的元素都 都放在了最終的位置上。 ?任何增量序列能使用，但必須保證 t1=1；當(dāng)增量序列為 1時(shí)，該算法就退化成直接插入排序了。amp。 } } 快速排序分析 ?當(dāng)初始序列有序或基本有序時(shí)，快速排序就接近于冒泡排序了，其時(shí)間復(fù)雜度為 O(n*n). ?該算法是霍爾 1962年提出的。 /*R[i+1]和 R[i+2]為根的左右子樹是 x=r[i]。 i) { r[1]?r[i]。 /*記錄 else r2[k++]=r[j++]。 ?一趟“分散”過程結(jié)束后，在此排列基礎(chǔ)上，再進(jìn)行下一趟檢查另一位數(shù)的“分散”。 /*隊(duì)列的頭 、 尾指示器 ， rd是基數(shù) ， 十進(jìn)制為 10*/ for (i=1。 while (f[j]==0) j++。 }。 2. 設(shè)計(jì)一個(gè)用單鏈表作存儲(chǔ)結(jié)構(gòu)的直接插入排序算法。 4. 已知序列 {491， 77， 572， 16， 996， 101， 863，258， 689， 325}，請(qǐng)分別給出采用快速