【正文】 增量的排序。 堆分為最大堆和最小堆，其實(shí)就是完全二叉樹。 本質(zhì)上講， 堆排序是一種選擇排序 ， 每次都選擇 堆中最大的元素進(jìn)行排序。 Zhijie(L)。 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 結(jié)束 假 開始 k=0 kt 第 7 頁 共 38 頁 冒泡算法功能描述 真 真 真 假 假 真 假 i= [i].key[idk].key [0]=[i]； j=idk； j0amp。 j [j].key[j+1].key [j] [j+1] 結(jié) 束 j++ i++ 第 9 頁 共 38 頁 快速排序算法功能描述 1算法功能描述 真 [0]=[low] Pivotkey=[low].key L,low,high Lowhigh [low]=[high] Lowhigh amp。 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 [ 0 ] . k e y L . r [ m ]. k e yh i g h = m 1 。是L . r [ h i g h + 1 ] = L . r [ 0 ] 。輸 入 8 f l a g = 1 。c = = 39。 L r [ i ] . o t h e r = r a n d ( ) % 2 6 + 6 5 。 //r[0]閑置或用作哨兵單元 int length。 ） include include include include iostream includealgorithm using namespace std。 //順序表長度 }SqList。 //記錄每個(gè)排序方法的 移動次數(shù)和比較次數(shù) int flag=0。 } } /*輸出元素 */ void visit(SqList L) {int i。 =0。k=。 } 第 21 頁 共 38 頁 } if(!flag) { printf(本次隨機(jī)數(shù)據(jù)排序的移動次數(shù)為 :)。} } //直接插入排序 void Zhijie(SqList L) { Recode r。++i) { // ++。 ++。 visit(L)。 //暫存 rmove ++。 } Lr[j+dk]=Lr[0]。kt。 printf(希爾排序后的結(jié)果 ： )。 RedType t。 [j]=[j+1]。 } else{num[6]=。Lr[high].key =pivotkey){ high。 //將比樞軸記錄大的記錄移到高端 rmove =rmove+2。 //對低子表遞歸排序 ， pivotloc是樞軸位置 QSort(L,pivotloc+1,high,r)。 printf(%d\n,)。L, int s, int m) { // 已知 [s..m]中記錄的關(guān)鍵字除 [s] 之外 //均滿足堆的特征，本函數(shù)自上而下調(diào)整 [s] //的關(guān)鍵字，使 [s..m] 也成為一個(gè)大頂堆 Recode r。 ++。 ++。 第 26 頁 共 38 頁 // 對順序表 L 進(jìn)行堆排序 for (int i=。 if (i!=1) {/*交換順序 */ //++。 printf(**本次排序的比較次數(shù)為 :)。 Recode r。 // 將 [i]暫存到 [0] low = 1。 // 插入點(diǎn)在高半?yún)^(qū) =+1。 } if(!flag) { printf(**本次排序的移動次數(shù)為 :)。} } // BInsertSort void print(int num[]) //打印排序方法比較表 { int k=0。 printf(\t|快速排序 | %5d | %5d |\n,num[8],num[9])。 printf(\t\t ★★★★★★★★★★★★★★★★★★★★★ \n)。L,length)。 scanf(%d,amp。 //希爾排序 break。 break。 QuickSort(L)。 }while(1)。) break。由以上運(yùn)行結(jié)果可分析出穩(wěn)定排序有 直接插入排序 和 冒泡排序 ，不穩(wěn)定排序有選擇排序，希爾排序和快速排序。 我們感受最深的一點(diǎn)是：以前用 C 編程，只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術(shù)，只是憑單 純的意識和簡單的語句來堆砌出一段程序。這次實(shí)驗(yàn)中我們也出現(xiàn)過一些錯(cuò)誤。 在這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中，我此次的題目是各種 排序，排序?qū)嶋H上是編程設(shè)計(jì)中應(yīng)用比較廣泛的知識，通過本次設(shè)計(jì)，我對一些基本的內(nèi)部排序有了很好的理解和掌握，并且通過此次課程設(shè)計(jì)中的程序運(yùn)行結(jié)果很好的理解了排序各種算法的穩(wěn)定性和時(shí)間復(fù)雜度，既鞏固了課堂上學(xué)到的排序理論，又為自己的編程增強(qiáng)了實(shí)踐。最后在編寫每一個(gè)函數(shù)之前，可以仔細(xì)斟酌比對，挑選出最適合當(dāng)前狀況的算法。當(dāng) n 較小時(shí)，對穩(wěn)定性不作要求時(shí)宜用選擇排序，對穩(wěn)定性有要求時(shí)宜用插入或冒泡排序。 }while(1)。 getchar()。 flag=0。 //折半插入排序 break。 //冒泡排序 break。 switch (select) { case 0:exit(0)。 visit(L)。 int select,length。 printf(\t|折 半插入排序 | %5d | %5d |\n,num[12],num[13])。 printf(\t|排序方法 | 關(guān)鍵字移動次數(shù) |關(guān)鍵字比較次數(shù) |\n)。 printf(**本次排序的比較次數(shù)為 :)。 } } for (j=i1。 while (low=high) { // ++。 =0。 printf(堆排序后的結(jié)果 ： )。 [1]=[i]。 i ) { ++。 // 將調(diào)整前的堆頂記錄插入到 s (注意插入的位置為 s j=2*s) ++。amp。 =0。 printf(%d\n,)。 =0。 //樞軸記錄到位 rmove ++。} Lr[low]=Lr[high]。} } //快速排序法 int Partition(SqList *L,int low,int high,Recode *r) { int pivotkey。 } } if(!flag) { printf(本次隨機(jī)數(shù)據(jù)排序的移動次數(shù)為 :)。i。 } else{num[4]=。L,dlta[k],amp。 } } } void ShellSort(SqList L,int dlta[],int t) { //按增量序列 dlta[0..t1]對順序表 L作希爾排序。j0amp。num[3]=。 //插入到正確位置 ++。 //復(fù)制為哨兵 [i]=[i1]。 =0。 printf(本次隨機(jī)數(shù)據(jù)排序的比較次數(shù)為 :)。 j=k。 int i,j,k。 for(i=1。 srand(time(0))。 /*記錄數(shù)據(jù)移動次數(shù) */ int p。} //定義一個(gè)帶參數(shù)的 宏，將數(shù)組長度存儲在變量 len 中 typedef int KeyType。 //順序表類型 typedef struct{ int move。 ） define MAX