【正文】 。break。break。 break。 }/*mergesort end*/ int yx(int m,int i) /*分離關(guān)鍵字倒數(shù)第 i位有效數(shù)字的算法 */ {int x。l=2*l。l=2*l。 l=1。 } }/*mergepass end*/ 第 9章 排 序 void mergesort(node a[?],int n) /*歸并排序的主體函數(shù) */ {int l。h2=n1。 else { h1=i。j=n。 i=i+2*l。h2=i+2*l1。 while ((ni)=2*l) {h1=i。} }/*merge end*/ void mergepass(node a[?],node a2[?],int l,int n) /*一趟歸并 */ 第 9章 排 序 {int j,i,h1,mid,h2。a2[k].key=a[j].key。i++。} } while (i=mid) {k++。} else {a2[k].key=a[j].key。 if (a[i].key=a[j].key) {a2[k].key=a[i].key。amp。k=h11。 i=h1。i++) a[i].key=a[i+1].key。 for (i=0。 heap(a,1,v1)。a[1].key=a[v].key。v) {printf(%5d,a[1].key)。 for(v=n。i) heap(a,i,n)。 for (i=n/2。i0。 第 9章 排 序 node x。 } a[i].key=。j=2*i。 if (a[j].key) {a[i].key=a[j].key。j=2*i。 int j。 quick2(a,i+1,h)。 if(lh) { i=hoare(a,l,h)。 printf(輸出非遞歸快速排序的結(jié)果 :\n)。top。 else {l=s[top][0]。h=h1。s[top][0]=i+1。 do {while (lh) {i=hoare(a,l,h)。tag=1。 l=0。 }/*hoare end*/ void quick1(node a[?],int n) /*非遞歸的快速排序主體函數(shù) */ {int i,l,h,tag,top。 第 9章 排 序 a[i].key=。j。 (a[i].key=)) i++。} while((ij) amp。 if(ij) {a[i].key=a[j].key。amp。=a[i].key。 i=l。 }/*shell end*/ int hoare(node a[?],int l,int h) /*分區(qū)處理函數(shù) */ {int i,j。i++) a[i].key=a[i+1].key。 } 第 9章 排 序 for (i=0。} a[j+k]=a[0]。 (j=0)) {a[j+k].key=a[j].key。 while((a[j].keya[0].key) amp。i++) {a[0].key=a[i].key。 while (k=1) {for (i=k+1。i) a[i].key=a[i1].key。 for(i=n。 } 第 9章 排 序 return(n)。 scanf(%d,amp。n++。i)。 printf(input keys:)。 }/*print*/ int creat(?) /*輸入待排序的記錄 */ {int i,n。i++) printf(%5d,a[i].key)。 第 9章 排 序 for (i=0。 case 7:radixsort(r,num)。print(r,num)。break。break。 printf(輸出非遞歸快速排序的結(jié)果 :\n)。h=num1。break。 case 3:quick1(r,num)。print(r,num)。break。printf(記錄中原始數(shù)據(jù)如下： \n)。c)。 printf(輸入選擇 (17,0 表示結(jié)束 ):)。 printf(6. 歸并排序 \n)。 printf(4. 遞歸的快速排序 \n)。 printf(2. 希爾排序 \n)。 第 9章 排 序 while (c!=0) {printf( 主菜單 )； printf(1. 輸入關(guān)鍵字，以 9999表示結(jié)束。 int num,l,h,c。 int yx(int m,int i)。 void mergepass(node a[?],node a2[?],int l,int n)。 void heapsort(node a[?],int n)。 void quick2(node a[?],int l,int h)。 int hoare(node a[?],int l,int h)。 int creat(?)。 node r[20]。 int point。 第 9章 排 序 有關(guān)排序算法的 C語(yǔ)言源程序 include include typedef struct /*記錄結(jié)構(gòu)。 (4) 當(dāng) n值很大并且關(guān)鍵字位數(shù)較小時(shí)，采用靜態(tài)鏈表基數(shù)排序較好。 第 9章 排 序 (3) 當(dāng) n值很大 ， 并對(duì)排序穩(wěn)定性有要求 ， 存儲(chǔ)容量較寬余時(shí) ， 用歸并排序最為合適 。一般來(lái)講，它們排序速度非?？?。 其中直接插入排序更為常用 。 它們的時(shí)間復(fù)雜度雖為 O(n2)，但方法簡(jiǎn)單易掌握 。 在不同的應(yīng)用條件下可選擇較合適的不同方法 ， 甚至可將多種方法結(jié)合使用 。它的空間占用情況是，向量 r多了 n個(gè)指針域，輔助空間為 2rd個(gè)隊(duì)列指針。 }/*yx*/ 第 9章 排 序 radixsort算法中基數(shù)為 10，這里用 rd表示它；最高有效數(shù)字位是 4，這里用 d表示，記錄總數(shù)為 n。 /*百位 */ case 4:x=(m%10000)/1000。 /*十位 */ case 3:x=(m%1000)/100。 /*個(gè)位 */ case 2:x=(m%100)/10。 /*基數(shù)排序結(jié)果 p指向靜態(tài)鏈表的第一個(gè)元素，即關(guān)鍵字最小的記錄 */ }/*radixsort*/ 第 9章 排 序 分離關(guān)鍵字倒數(shù)第 i位有效數(shù)字算法： 算法 int yx(int m,int i) {switch (?) {case 1:x=m%10。} /*將前邊一個(gè)非空隊(duì)列的隊(duì)尾元素指針指向現(xiàn)在隊(duì)頭元素并記下現(xiàn)在隊(duì)尾位置 */ 第 9章 排 序 r[t].point=0。 if (f[j]!=0) {r[t].point=f[j]。amp。 /*p記下隊(duì)頭做收集后的靜態(tài)鏈表頭指針 */ while (j10) { j++。 /*找第一個(gè)非空隊(duì)列 */ p=f[j]。 /*在 r向量中， p指針向后移 */ } 第 9章 排 序 /*下面是收集 */ j=0。 e[k]=p。} /*讓頭尾指針指向同一元素 */ else {l=e[k]。 /*取關(guān)鍵字倒數(shù)第 i位有效數(shù)字 */ if (f[k]==0) {f[k]=p。e[j]=0。j10。i=d。p=1。i++) r[i].point=i+1。 for (i=1。 /*其他信息域 */ int point。記錄結(jié)構(gòu)為： struct node {int key。這種結(jié)構(gòu)稱為靜態(tài)鏈表結(jié)構(gòu) 。 本節(jié)不采用動(dòng)態(tài)鏈表而仍用向量 r存儲(chǔ) (即一維數(shù)組 )， 讓每個(gè)存放記錄的數(shù)組元素增加一個(gè)指針域 。 第 9章 排 序 在本章前幾節(jié)的討論中 ， 待排序的記錄是用向量 r做存儲(chǔ)結(jié)構(gòu) 。 圖 (f)則是按百位上的有效數(shù)字分配之后的各隊(duì)列狀態(tài)。 第 9章 排 序 圖 (d)是按每個(gè)關(guān)鍵字十位上的有效數(shù)字重新將它們分配到相應(yīng)的隊(duì)列中去 ， 例如 ， 關(guān)鍵字 58 18 083都分配到了 8號(hào)隊(duì)列中去 。例如，關(guān)鍵字 008， 278都分配到了 8號(hào)隊(duì)列中去，e[8]指向隊(duì)尾， f[8]指向隊(duì)頭。 圖 (a)是待排序的關(guān)鍵字序列的初始狀態(tài)。 第 9章 排 序 例 有一組關(guān)鍵字{278,109,063,930,589,184,505,269,008,083}，將它們按由小到大的順序排序。此序列若觀察其關(guān)鍵字的個(gè)位 ， 則它是有序的；若觀察其關(guān)鍵字的高位 ， 則它尚處于無(wú)序狀態(tài) 。 例如 ， 關(guān)鍵字為184的記錄就分配到 4號(hào)隊(duì)列中去 。 第 9章 排 序 算法思路： (1) 第一趟 “ 分配 ” ， 根據(jù)關(guān)鍵字的個(gè)位有效數(shù)字 ， 把所有記錄分配到相應(yīng)的 10個(gè)隊(duì)列中去 。假設(shè)有 n個(gè)記錄，其關(guān)鍵字在0～ 999之間，每一位上有效數(shù)字值在 0～ 9之間共 10種可能性，則認(rèn)為基數(shù)是 10，在進(jìn)行“分配”操作時(shí)涉及 10個(gè)隊(duì)列，即隊(duì)列的個(gè)數(shù)與基數(shù)相同。 第 9章 排 序 另一方法是首先根據(jù)關(guān)鍵字的最低位 (個(gè)位 )有效數(shù)字進(jìn)行排序 ， 然后根據(jù)次低位 (十位 )有效數(shù)字進(jìn)行排序 ， 依次類(lèi)推 ， 直到根據(jù)最高位有效數(shù)字進(jìn)行排序 ， 產(chǎn)生一個(gè)有序序列 ， 這種方法稱最低位優(yōu)先法 (Least Significant Digit)， 簡(jiǎn)稱 LSD法 。 第 9章 排 序 基 數(shù) 排 序 本章假設(shè)記錄的關(guān)鍵字為整型 (實(shí)質(zhì)上關(guān)鍵字并不限于整型 )。該算法需占用與待排序記錄相等的輔助向量空間。每一趟處理考慮兩兩子表歸并，其運(yùn)算數(shù)量級(jí)為 O(n)。r2[k]=r[t]。t=h2。r2[k]=r[t]。t=mid。j++。} while (j=h2) {k++。r2[k]=r[i]。j++。i++。 (j=h2)) { k=k+1。 /*k是 r2的初始指針 */ while ((i=mid) amp。j=mid+1。 merge(r,r2,h1,mid,h2)。mid=h1+l1。j=n。 i=i+2*l。h2=i+2*l1。 /*從第一個(gè)記錄開(kāi)始 */ while ((ni+1)=2*l) { /*剩下的記錄數(shù)目大于兩個(gè)子表長(zhǎng)度時(shí) */ h1=i。l=l*2。l=l*2。 第 9章 排 序 主體框架算法描述如下： 算法 void mergesort(node r[?],int n) /*r是包含有 n個(gè)記錄的原文件，歸并過(guò)程中另需一個(gè) r2作為輔助存儲(chǔ)空間 */ {l=1。然后對(duì)于某確定的子表表長(zhǎng) L，將 n個(gè)記錄分成若干組子表，兩兩歸并，這里顯然要循環(huán)若干次，把這一步寫(xiě)成一個(gè)函數(shù) mergepass，可由 mergesort調(diào)用。 圖 兩路歸并示例 初 始第 一 趟[ 4 ] [ 7 ] [ 5 ] [ 3 ] [ 2 ] [ 8 ] [ 6 ] [ 1 ] L ＝ 1[4 7] [3 5] [2 8] [1 6] L ＝ 2第 二 趟 4 5 7] [1 2 6 8] L ＝ 4[3第 三 趟 [1 2 3 4 5 6 7 8] L ＝ n第 9章 排 序 算法實(shí)現(xiàn)：此算法的實(shí)現(xiàn)不像圖示那樣簡(jiǎn)單，現(xiàn)分三步來(lái)討論。 第 9章 排 序 例 有一組關(guān)鍵字 {4,7,5,3,2,8,6,1}， n=8，將其按由小到大的順序排序。 這里僅對(duì)內(nèi)排序的兩路歸并方法進(jìn)行討論 。 歸并的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表 。堆排序的部分處理過(guò)程如圖。設(shè)有一組關(guān)鍵字： {6， 7， 51， 2， 52， 8}，經(jīng)排序后的結(jié)果是：{2， 52， 51， 6， 7， 8}。在內(nèi)存空間占用方面，基本沒(méi)有外增的輔助空間，僅有一個(gè) x。堆排序中heap算法的時(shí)間復(fù)雜度與堆所對(duì)應(yīng)的完全二叉樹(shù)的樹(shù)高度 lbn相關(guān)。 }/*heapsort*/