【正文】 題描述 ......................................................................................................................... 1 基本要求： ...................................................................................................................... 1 . 算法思想： ..................................................................................................................... 1 . 模塊劃分： ..................................................................................................................... 3 . 數(shù)據(jù)結構： ................................................................................................................... 18 . 源程序： ....................................................................................................................... 19 . 測試情況： ................................................................................................................... 30 三、小結 ....................................................................................................................................... 37 四、參考文獻 ............................................................................................................................... 38 一、 問題描述 用 C 語言編程解決 插入、 冒泡，快速排序，簡單選擇，堆排序 以及分析各種算法的時間復雜度和空間復雜度，比較 各種排序在不同場合的適用程度，分析各種排序算法的 實用性 。 希爾排序 1 基本思想 希爾排序法是 1959 年由 ,又稱減少增量的排序。 遞歸求解 (Conquer)：通過遞歸調(diào)用快速排序算法分別對 L[p..q]和 L[q+1..r]進行排序。 堆分為最大堆和最小堆，其實就是完全二叉樹。 或者說，堆排序?qū)⑺械拇判驍?shù)據(jù)分為兩部分，無序區(qū)和有序區(qū)。 本質(zhì)上講， 堆排序是一種選擇排序 ， 每次都選擇 堆中最大的元素進行排序。 BinsertSort() select Exit(0) select_sort(L)。 Zhijie(L)。 print(num)。 k=i+1 k++ [i] [j] i++ 假 開始 i=2 i= 第 6 頁 共 38 頁 希爾排序算法功能描述 真 真 假 假 真 [i].key[i1].key [0]=[i]； [i]=[i1]； j=i2； [0].key[j].key [j+1]=[j]； j； [j+1]=[0] ++i 結束 假 開始 k=0 kt 第 7 頁 共 38 頁 冒泡算法功能描述 真 真 真 假 假 真 假 i= [i].key[idk].key [0]=[i]； j=idk； j0amp。r)。 j [j].key[j+1].key [j] [j+1] 結 束 j++ i++ 第 9 頁 共 38 頁 快速排序算法功能描述 1算法功能描述 真 [0]=[low] Pivotkey=[low].key L,low,high Lowhigh [low]=[high] Lowhigh amp。[high].key=pivotkey 77 第 10 頁 共 38 頁 2算法描述 真 假 L， low， high Lowhigh Pivotloc=partioion(L,low,high),low=low, high=pivotloc1。 L . r [ j ] . k e y L . r [ j + 1] . k e y+ + j L . r [ s ] = L . r [ j ] 。 L . r [ 1 ] ← → L . r [ i ] 。 L . r [ 1 ] = L . r [ i ] 。否是結 束 第 13 頁 共 38 頁 第 14 頁 共 38 頁 折半插入排序 第 15 頁 共 38 頁 開 始 i = 2 , j , h i g h , l o w , m 。 是L . r [ 0 ] . k e y L . r [ m ]. k e yh i g h = m 1 。 r . m o v e + + 。是L . r [ h i g h + 1 ] = L . r [ 0 ] 。輸 入 S e l e c t（ 0 8 ）輸 入 0退 出輸 入 1s e l e c t _ s o r t ( L ) 。輸 入 8 f l a g = 1 。 p r i n t ( n u m ) 。c = = 39。結 束開 始輸 入 3 S h e l l S o r t ( L , d l t a , 5 ) 。 L r [ i ] . o t h e r = r a n d ( ) % 2 6 + 6 5 。 typedef struct //定義存儲記錄關鍵字及其他信息的結構體 { KeyType key。 //r[0]閑置或用作哨兵單元 int length。 /*記錄數(shù)據(jù)比較次數(shù) */ 第 19 頁 共 38 頁 int pex。 ） include include include include iostream includealgorithm using namespace std。 char other。 //順序表長度 }SqList。 /*記錄空間復雜度 */ }Recode。 //記錄每個排序方法的 移動次數(shù)和比較次數(shù) int flag=0。 for(i=1。 } } /*輸出元素 */ void visit(SqList L) {int i。i++) printf(%4d%2c,[i].key,[i].other)。 =0。 for (i=1。k=。 t=[j]。 } 第 21 頁 共 38 頁 } if(!flag) { printf(本次隨機數(shù)據(jù)排序的移動次數(shù)為 :)。 printf(簡單選擇排序后的結果： )。} } //直接插入排序 void Zhijie(SqList L) { Recode r。 int j。++i) { // ++。 for(j=i2。 ++。 printf(%d\n,)。 visit(L)。 for(i=dk+1。 //暫存 rmove ++。(Lr[0].key Lr[j].key)。 } Lr[j+dk]=Lr[0]。 =0。kt。//一趟增量為 dlta[k]的插入排序 if(!flag) { printf(本次隨機數(shù)據(jù)排序的移動次數(shù)為 :)。 printf(希爾排序后的結果 ： )。} } //冒泡排序法 void Maopao(SqList L) { Recode r。 RedType t。j=。 [j]