【正文】 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)缺點(diǎn) ， 沒有哪一種排序方法絕對最優(yōu) 。 在不同的應(yīng)用條件下可選擇較合適的不同方法 ， 甚至可將多種方法結(jié)合使用 。 (1) 當(dāng)問題的規(guī)模不大 ， 即待排序的記錄數(shù) n不大時 (n≤50)， 可選用表中前三種排序方法之一 。 它們的時間復(fù)雜度雖為 O(n2)，但方法簡單易掌握 。 直接插入排序和冒泡排序在原文件記錄按關(guān)鍵字 “ 基本有序 ” 時 ， 排序速度比較快 。 其中直接插入排序更為常用 。 (2) 當(dāng) n值很大，并不強(qiáng)求排序穩(wěn)定性，并且內(nèi)存容量不寬余時，應(yīng)該選用快速排序或堆排序。一般來講，它們排序速度非?？?。但快速排序?qū)υ蛄谢居行虻那闆r，速度減慢接近O(n2)，而堆排序不會出現(xiàn)最壞情況。 第 9章 排 序 (3) 當(dāng) n值很大 ， 并對排序穩(wěn)定性有要求 ， 存儲容量較寬余時 ， 用歸并排序最為合適 。 排序速度很快 ， 并且穩(wěn)定性好 。 (4) 當(dāng) n值很大并且關(guān)鍵字位數(shù)較小時，采用靜態(tài)鏈表基數(shù)排序較好。不僅速度較快并且穩(wěn)定性好。 第 9章 排 序 有關(guān)排序算法的 C語言源程序 include include typedef struct /*記錄結(jié)構(gòu)。為簡化問題，設(shè)定記錄中只含關(guān)鍵字 */ {int key。 int point。 /*該域用于基數(shù)排序 */ }node。 node r[20]。 main(?) { void print(node a[?],int n)。 int creat(?)。 第 9章 排 序 void shell(node a[?],int n)。 int hoare(node a[?],int l,int h)。 void quick1(node a[?],int n)。 void quick2(node a[?],int l,int h)。 void heap(node a[?],int i,int m)。 void heapsort(node a[?],int n)。 void merge(node a[?],node a2[?],int h1,int mid,int h2)。 void mergepass(node a[?],node a2[?],int l,int n)。 void mergesort(node a[?],int n)。 int yx(int m,int i)。 int radixsort(node a[?],int n)。 int num,l,h,c。 c=1。 第 9章 排 序 while (c!=0) {printf( 主菜單 )； printf(1. 輸入關(guān)鍵字，以 9999表示結(jié)束。 \n)。 printf(2. 希爾排序 \n)。 printf(3. 非遞歸的快速排序 \n)。 printf(4. 遞歸的快速排序 \n)。 printf(5. 堆排序 \n)。 printf(6. 歸并排序 \n)。 printf(7. 基數(shù)排序 \n)。 printf(輸入選擇 (17,0 表示結(jié)束 ):)。 scanf(%d,amp。c)。 switch(c) {case 1:num=creat(?)。printf(記錄中原始數(shù)據(jù)如下： \n)。 print(r,num)。break。 第 9章 排 序 case 2:shell(r,num)。print(r,num)。break。 case 3:quick1(r,num)。print(r,num)。break。 case 4:l=0。h=num1。quick2(r,l,h)。 printf(輸出非遞歸快速排序的結(jié)果 :\n)。 print(r,num)。break。 case 5:heapsort(r,num)。break。 case 6:mergesort(r,num)。print(r,num)。break。 case 7:radixsort(r,num)。 } } }/*main end*/ void print(node a[?],int n) /*打印記錄 */ {int i。 第 9章 排 序 for (i=0。in。i++) printf(%5d,a[i].key)。 printf(\n)。 }/*print*/ int creat(?) /*輸入待排序的記錄 */ {int i,n。 n=0。 printf(input keys:)。 scanf(%d,amp。i)。 while (i!=9999) {r[n].key=i。n++。 printf(input keys:)。 scanf(%d,amp。i)。 } 第 9章 排 序 return(n)。 }/*creat end*/ void shell(node a[?],int n) /*希爾排序 */ {int i,j,k。 for(i=n。i=1。i) a[i].key=a[i1].key。 k=n/2。 while (k=1) {for (i=k+1。i=n。i++) {a[0].key=a[i].key。j=ik。 while((a[j].keya[0].key) amp。amp。 (j=0)) {a[j+k].key=a[j].key。j=jk。} a[j+k]=a[0]。 } k=k/2。 } 第 9章 排 序 for (i=0。in。i++) a[i].key=a[i+1].key。 printf(輸出希爾排序的結(jié)果 :\n)。 }/*shell end*/ int hoare(node a[?],int l,int h) /*分區(qū)處理函數(shù) */ {int i,j。 node x。 i=l。j=h。=a[i].key。 do{ while((ij) amp。amp。 (a[j].key=)) j。 if(ij) {a[i].key=a[j].key。i++。} while((ij) amp。amp。 (a[i].key=)) i++。 if (ij) {a[j].key=a[i].key。j。} }while (ij)。 第 9章 排 序 a[i].key=。return(i)。 }/*hoare end*/ void quick1(node a[?],int n) /*非遞歸的快速排序主體函數(shù) */ {int i,l,h,tag,top。 int s[20][2]。 l=0。h=n1。tag=1。top=0。 do {while (lh) {i=hoare(a,l,h)。 top++。s[top][0]=i+1。 s[top][1]=h。h=h1。 } if(top==0) tag=0。 else {l=s[top][0]。 第 9章 排 序 h=s[top][1]。top。 } }while (tag==1)。 printf(輸出非遞歸快速排序的結(jié)果 :\n)。 }/*quick1 end*/ void quick2(node a[?],int l,int h) /*遞歸的快速排序主體函數(shù) */ {int i。 if(lh) { i=hoare(a,l,h)。 quick2(a,l,i1)。 quick2(a,i+1,h)。 } 第 9章 排 序 }/*quick2 end*/ void heap(node a[?],int i,int m) /*調(diào)整堆的函數(shù) */ { node x。 int j。 =a[i].key。j=2*i。 while (j=m) {if (jm) if (a[j].keya[j+1].key) j++。 if (a[j].key) {a[i].key=a[j].key。i=j。j=2*i。} else j=m+1。 } a[i].key=。 }/*heap end*/ void heapsort(node a[?],int n) /*堆排序的主體函數(shù) */ {int i,v。 第 9章 排 序 node x。 for (i=n。i0。i) a[i].key=a[i1].key。 for (i=n/2。i=1。i) heap(a,i,n)。 printf(輸出歸并排序的結(jié)果 :\n)。 for(v=n。v=2。v) {printf(%5d,a[1].key)。 =a[1].key。a[1].key=a[v].key。 a[v].key=。 heap(a,1,v1)。 } printf(%5d,a[1].key)。 for (i=0。in。i++) a[i].key=a[i+1].key。 }/*heapsort end*/ 第 9章 排 序 void merge(node a[?],node a2[?],int h1,int mid,int h2) /*歸并排序的核心算法 */ {int i,j,k。 i=h1。j=mid+1。k=h11。 while ((i=mid) amp。amp。 (j=h2)) {k=k+1。 if (a[i].key=a[j].key) {a2[k].key=a[i].key。i++。} else {a2[k].key=a[j].key。j++。} } while (i=mid) {k++。a2[k].key=a[i].key。i++。} while (j=h2) {k++。a2[k].key=a[j].key。j++。} }/*merge end*/ void mergepass(node a[?],node a2[?],int l,int n) /*一趟歸并 */ 第 9章 排 序 {int j,i,h1,mid,h2。 i=0。 while ((ni)=2*l) {h1=i。mid=h1+l1。h2=i+2*l1。 merge(a,a2,h1,mid,h2)。 i=i+2*l。 } if ((ni)=l) for (j=i。j=n。j++) a2[j].key=a[j].key。 else { h1=i。mid=h1+l1。h2=n1。 merge(a,a2,h1,mid,h2)。 } }/*mergepass end*/ 第 9章 排 序 void mergesort(node a[?],int n) /*歸并排序的主體函數(shù) */ {int l。 node a2[20]。 l=1。 while (ln) {mergepass(a,a2,l,n)。l=2*l。 mergepass(a2,a,l,n)。l=2*l。 } printf(輸出歸并排序的結(jié)果 :\n)。 }/*mergesort end*/ int yx(int m,int i) /*分離關(guān)鍵字倒數(shù)第 i位有效數(shù)字的算法 */ {int x。 switch(i) 第 9章 排 序 {case 1:x=m%10。 break。 case 2:x=(m%100)/10。break。 case 3:x=(m%1000)/100。break。 case 4:x=(m%10000)/1000。