【正文】 case 4:x=(m%10000)/1000。 case 2:x=(m%100)/10。 } printf(輸出歸并排序的結(jié)果 :\n)。 while (ln) {mergepass(a,a2,l,n)。 merge(a,a2,h1,mid,h2)。j++) a2[j].key=a[j].key。 merge(a,a2,h1,mid,h2)。 i=0。} while (j=h2) {k++。j++。 (j=h2)) {k=k+1。j=mid+1。in。 a[v].key=。v=2。i=1。 for (i=n。} else j=m+1。 while (j=m) {if (jm) if (a[j].keya[j+1].key) j++。 } 第 9章 排 序 }/*quick2 end*/ void heap(node a[?],int i,int m) /*調(diào)整堆的函數(shù) */ { node x。 }/*quick1 end*/ void quick2(node a[?],int l,int h) /*遞歸的快速排序主體函數(shù) */ {int i。 第 9章 排 序 h=s[top][1]。 s[top][1]=h。top=0。 int s[20][2]。} }while (ij)。amp。 (a[j].key=)) j。j=h。 printf(輸出希爾排序的結(jié)果 :\n)。 } k=k/2。amp。i=n。i=1。i)。 while (i!=9999) {r[n].key=i。 n=0。in。break。 case 5:heapsort(r,num)。quick2(r,l,h)。print(r,num)。 第 9章 排 序 case 2:shell(r,num)。 switch(c) {case 1:num=creat(?)。 printf(7. 基數(shù)排序 \n)。 printf(3. 非遞歸的快速排序 \n)。 c=1。 void mergesort(node a[?],int n)。 void heap(node a[?],int i,int m)。 第 9章 排 序 void shell(node a[?],int n)。 /*該域用于基數(shù)排序 */ }node。不僅速度較快并且穩(wěn)定性好。但快速排序?qū)υ蛄谢居行虻那闆r，速度減慢接近O(n2)，而堆排序不會出現(xiàn)最壞情況。 直接插入排序和冒泡排序在原文件記錄按關(guān)鍵字 “ 基本有序 ” 時 ， 排序速度比較快 。 第 9章 排 序 內(nèi)部排序總結(jié) 表 各種排序方法性能的比較表 排序方法 時間復(fù)雜度 特殊情況 輔助空間 穩(wěn)定性 直接插入排序 O (n2) 原表有序 O (n ) O (1 ) 穩(wěn)定 簡單選擇排序 O (n2) O (n2) O (1 ) 穩(wěn)定 冒泡排序 O (n2) 原表有序 O (n ) O (1 ) 穩(wěn)定 希爾排序 O (n1. 3) / O (1 ) 不穩(wěn)定 快速排序 O (n l b n ) 原表有序 O (n2) O (n l b n ) 或 O (n ) 不穩(wěn)定 堆排序 O (n l b n ) O (n l b n ) O (1 ) 不穩(wěn)定 兩路歸并排序 O (n l b n ) O (n l b n ) O (n ) 穩(wěn)定 基數(shù)排序 O( d (n + rd )) O (d (n + rd )) O (rd ) 穩(wěn)定 第 9章 排 序 本章介紹的排序方法各有優(yōu)缺點 ， 沒有哪一種排序方法絕對最優(yōu) 。 /*千位 */ } return(x)。break。 /*這是一趟分配與收集之后的鏈表最后一個元素 */ } } /* for i */ return(p)。 (f[j]==0) j++。 t=e[j]。} /*在 k號隊列尾部入隊 */ p=r[p].point。 e[k]=p。j++) {f[j]=0。 /*建立靜態(tài)鏈表， p指向鏈表的第一個元素 */ for (i=1。in。 /*關(guān)鍵字域 */ int oth。 此域為整型 ， 用來存放該記錄的下一個相鄰記錄所在數(shù)組元素的下標(biāo) 。圖 (g)則是再次收集后的結(jié)果，這也是基數(shù)排序所得到的最終的有序序列。 圖 (c)是將 6個非空隊列 (0號， 3號， 4號， 5號， 8號， 9號 )頭尾相接收集在一起之后得到的一個新的序列。 操作的具體過程見圖 。 (2) 第一趟 “ 收集 ” 把所有非空隊列 (10個隊列中可能有空隊 )按隊列號由小到大的順序頭 、 尾相接 ， 收集成一個新的序列 。此處關(guān)鍵字最多位數(shù)是 3，那么就需進行 3趟“分配”和“收集”操作?；鶖?shù)排序有兩種方法： 一種方法是首先根據(jù)最高位有效數(shù)字進行排序，然后根據(jù)次高位有效數(shù)字進行排序，依次類推，直到根據(jù)最低位 (個位 )有效數(shù)字進行排序，產(chǎn)生一個有序序列，這種方法稱最高位優(yōu)先法 (Most Significant Digit first)，簡稱 MSD法。故歸并排序時間復(fù)雜度為 O(n lbn)。t++) {k++。t++) {k++。r[2]=r[j]。} } while (i=mid) {k++。 if (r[i].key=r[j].key) {r2[k]=r[i]。k=h11。h2=n。 /*跳過兩個子表 ， 指向新的一對子表的首記錄 */ } if ((ni+1)=l) /*剩下的記錄數(shù)目小于一個子表時 */ for (j=i。 mid=h1+l1。 /*r向量歸并排序到 r2向量中，子表長度加倍 */ mergepass(r2,r,l,n)。最后再看每一組 (一對 )子表的歸并，其原理是相同的，只是子表表長不同，換句話說，是子表的首記錄號與尾記錄號不同，把這個歸并操作作為核心算法寫成函數(shù) merge，由 mergepass來調(diào)用。 兩路歸并排序操作過程如圖 ，其中 L為子表長度。 歸并排序有多路歸并排序 、 兩路歸并排序；可用于內(nèi)排序 ， 也可以用于外排序 。本來 51在前面，排序后 52移到 51的前面，所以說堆排序是不穩(wěn)定的。而 heapsort中對 heap的調(diào)用數(shù)量級為 n，所以堆排序的整個時間復(fù)雜度為 O(nlbn)。 /*本次比上次少處理一個記錄 */ } printf(%5d,r[1].key)。 /*輸出堆頂元素 */ x=r[1]。i) heap(r,i,n)。} /*向下一層探測 */ else j=m+1。 /*x保存根記錄內(nèi)容， j為左孩子編號 */ while (j=m) {if (jm) if (r[j].key)r[j+1].key) j++。 另外 ， 當(dāng)然還需再設(shè)計一個主體算法 ， 在初建堆階段 ，讓 i從 n/2變化到 1， 循環(huán)調(diào)用函數(shù) heap；在堆排序階段 ， 每輸出一次堆頂元素同時將堆尾元素與堆頂對換之后 ， 就調(diào)用一次 heap函數(shù)來恢復(fù)堆 ?；謴?fù)堆的過程與初建堆中 i=1時所進行的操作完全相同。此時需要讓 kz與更下一層的左、右孩子的關(guān)鍵字進行比較，直到某一層的左、右孩子的關(guān)鍵字不小于 kz，或左、右孩子不存在為止。例如 i=4時， k4k8(4280)，就不用調(diào)整，見圖(a)。 第一步：初建堆。 此時可能會反復(fù)調(diào)整某些結(jié)點 ， 直到 i=1為止 ， 堆初步建成 。 堆排序大體分兩步處理 。因此，也可借助完全二叉樹來描述堆的概念。圖 中的存儲狀態(tài)。若是一個上大、底小的堆，只需把“ ≤”改為“ ≥”即可。 r[i]=r[z]。 for (j=i+1。圖 5個關(guān)鍵字 {3,4,1,5,2}的簡單選擇排序過程的示意圖。如此進行選擇和調(diào)換 n2趟。例如，對一個表排序時總是取子區(qū)間的最后一個記錄的關(guān)鍵字，那么“比較”操作應(yīng)該從子區(qū)間左端開始。 排序過程簡述如下： 6 7 51 2 52 8 初始狀態(tài) [52 7 51] 6 [?7 8] [2] 52 [?51] 6 7 [8] [2 52 51 6 7 8] 最后狀態(tài) 第 9章 排 序 從這個例子可以分析出快速排序法的穩(wěn)定性問題 ， 其中 51和52表示兩個關(guān)鍵字的值相同 ， 都是 5。試分析，當(dāng)原文件關(guān)鍵字有序時，快速排序時間復(fù)雜度是 O(n2)，這種情況下快速排序不快。在最壞情況下，比如原文件關(guān)鍵字已經(jīng)有序，每次分區(qū)處理僅能得到一個子區(qū)。 輸出 r。h=n。 若要調(diào)用遞歸算法 ， 因函數(shù)的形參不同 ， 需做預(yù)處理 。 /*棧不空繼續(xù)循環(huán) */ } /*quicksort1*/ 第 9章 排 序 (2) 遞歸算法： 算法 void quicksort2(node r[?],int l,int h) { if(lh){ i=hoare(r,l,h)。 else { l=s[top][0]。s[top][0]=i+1。tag=1。 } /*hoare*/ 第 9章 排 序 2) 快速排序主體框架算法 對一個文件，令 l=1， h=n，調(diào)用 hoare，求出 i；然后右子區(qū) l=i+1， h=n，入棧；對左子區(qū)令 l=1， h=i1，再次調(diào)用 hoare，如此反復(fù)，直到全部文件記錄處理完畢。 j。} while((ij) amp。amp。 第 9章 排 序 ( 0 ) 46 56 14 43 95 10 19 72( 1 ) 56 14 43 95 10 19 72( 2 ) 56 14 43 95 1019 72( 3 ) 19 14 43 95 10 56 72( 4 ) 10 14 43 95 56 72( 5 ) 10 14 4319 95 56 7219( 6 ) 10 14 4 3 ][ 1 9 [ 9 5 56 7 2 ]46ji jiiiiijjj jjii46 移 x 單元， i = 1 ， j = 8 j = n ， 72 ＞ 46 ， 72 不動修改 j ， 10 ＜ 46 ， 10 移左邊修改 i ， 14 ＜ 46 ， 14 不動修改 i ， 43 ＜ 46 ， 43 不動 , 修改 i ， 95 ＞ 46 ， 95 移右邊修改 j ， i = j ， 46 填此處生成 2 個 子 文 件 ， 46 居中修改 j ， 19 ＜ 46 ， 19 移左邊修改 i ， 56 ＞ 46 ， 56 移右邊圖 快速排序分區(qū)處理 第 9章 排 序 算法 int hoare(node r[?],int l,int h) {i=1。第一個關(guān)鍵字 46作為控制字，該關(guān)鍵字所屬的記錄另存儲在一個 x變量中?，F(xiàn)在設(shè)計一個函數(shù) hoare，它僅對某一待排序文件進行左、右子區(qū)的劃分，使控制字居中；再設(shè)計一個主體框架函數(shù)quicksort，在這里多次調(diào)用 hoare函數(shù)以實現(xiàn)對整個文件的排序。 (2) 將右區(qū)首、尾指針 (記錄的下標(biāo)號 )保存入棧，對左區(qū)進行與第 (1)步相類似的處理，又得到它的左子區(qū)和右子區(qū)，控制字居中。由于其排序速度快 ， 因此稱快速排序 (quick sort)。所以外循環(huán)結(jié)束條件是：或者 tag=0，已有序；或者 i=n，已進行了 n1趟處理。 }while (tag==1 amp。r[j]=r[j1]。 do{ tag=0。圖中凡畫有弧線的，表示記錄發(fā)生過交換。 (3) 讓 j取 n至 i+1， 經(jīng)過一系列對比交換之后 ， r[i]之中是剩余若 干 記 錄 中 關(guān) 鍵 字 最 小 的 記 錄 。 第 9章 排 序 排序的算法思路是： (1) 讓 j取 n至 2， 將 r[j].key與 r[j1].key比較 ， 如果 r[j].keyr[j1].key， 則把記錄 r[j]與 r[j1]交換位置 ， 否則不進行交換 。有人在大量實驗基礎(chǔ)上推出，它的時間復(fù)雜度為 O()。 當(dāng) K=1時 ， 此算法就等同于直接插入排序方法 。 for所構(gòu)成的循環(huán)是針對某一特定的增量 k， 進行大跨步跳躍式的插入排序 。這里 n=8，取 d1 =4， d2=2，d3 =1，其排序過程如圖 。