【正文】 ★★★★★★★★★ \n)。 printf(\t\t ★ ★ \n)。 printf(\t\t ★ 本組數(shù)據(jù)排序方法比較表 ★ \n)。 printf(\t\t ★ ★ \n)。 printf(\t\t ★★★★★★★★★★★★★★★★★★★★★ \n)。 } void main() { char c。 int select,length。 SqList L。 do { printf(請輸入需排序的數(shù)據(jù) 個數(shù) (小于 200)： \n)。 scanf(%d,amp。length)。 第 29 頁 共 38 頁 create(amp。L,length)。 printf(產(chǎn)生的隨機序列為： \n)。 visit(L)。 do { printf(\n\n ****************** 歡 迎 進 入 排 序 系 統(tǒng) *******************\n )。 printf( ★ 1 選擇排序 排序 ★ \n )。 printf( ★ 5 快速排序 6 堆排序 上排序 ★ \n )。 printf( ★ ★ ★ ★ ★ ★ \n )。 printf( Please input number（ 07） \n)。 scanf(%d,amp。select)。 switch (select) { case 0:exit(0)。 case 1: select_sort(L)。 //選擇排序 break。 case 2: Zhijie(L)。 //直接插入排序 break。 case 3: ShellSort(L,dlta,5)。 //希爾排序 break。 case 4: Maopao(L)。 //冒泡排序 break。 case 5: QuickSort(L)。 //快速排序 break。 case 6: HeapSort ( L )。//堆排序 printf(最終排序結(jié)果為 :)。 visit(L)。 break。 case 7: BInsertSort(L)。 //折半插入排序 break。 case 8: //比較以上排序 第 30 頁 共 38 頁 flag=1。 select_sort(L)。 Zhijie(L)。 ShellSort(L,dlta,4)。 Maopao(L)。 QuickSort(L)。 print(num)。 flag=0。 break。 case 9: //更改數(shù)據(jù) break。 default:printf(輸入錯誤！請重新輸入 ....\n)。 break。 } if(select==8) break。 }while(1)。 printf(是否更換數(shù)據(jù)重新進行排序？ (y/n))。 getchar()。 c=getchar()。 if(c==39。n39。||c==39。N39。) break。 system(cls)。 }while(1)。 } . 測試情況： （ 設(shè)計測試數(shù)據(jù)，或具體給出測試數(shù)據(jù)。要求測試數(shù)據(jù)能全面地測試所設(shè)計程序的功能。最后 給出程序的測試情況，并分析運行結(jié)果。 ） 測試數(shù)據(jù)的設(shè)計 本程序的測試數(shù)據(jù)隨機生成 0 到 200 之內(nèi)的數(shù)據(jù) 圖 生成測試數(shù)據(jù)，進入排序系統(tǒng) 第 31 頁 共 38 頁 程序運行結(jié)果分析 1 選擇排序 2 直接插入排序 3希爾排序 4冒泡排序 第 32 頁 共 38 頁 5快速排序 6堆排序 第 33 頁 共 38 頁 7折半插入排序 第 34 頁 共 38 頁 8比較上述排序 分別測試幾組帶排序序列個數(shù)不同的序列，排序比較如下： 圖為： 5個數(shù)字排序比較結(jié)果 第 35 頁 共 38 頁 圖為： 9個數(shù)字排序比較結(jié)果 圖為： 20個數(shù)字排序比較結(jié)果 第 36 頁 共 38 頁 圖為： 100個數(shù)字排序比較結(jié)果 圖為： 200個數(shù)字排序比較結(jié)果 分析： 由以上運行結(jié)果可以看出排序算法的穩(wěn)定性和其時間復(fù)雜度。例如，在選擇排序中當(dāng)關(guān)鍵 字為 450 時，存在兩個此信息，一個為 D，另一個為 A，排序前 D 在 A 的前面，排序后 D 在 A 的后面，故可知選擇排序為不穩(wěn)定的排序。由以上運行結(jié)果可分析出穩(wěn)定排序有 直接插入排序 和 冒泡排序 ，不穩(wěn)定排序有選擇排序，希爾排序和快速排序。 由排序方法的比較表可 知 插入、冒泡排序的速度較慢。當(dāng) n 較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。當(dāng) n較大時，關(guān)鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序?？焖倥判蚴悄壳盎?于 比較的內(nèi)部排序法中被認為是最好的方法。 第 37 頁 共 38 頁 通過比較他們在不同場合的時間復(fù)雜度，得知 沒有哪一種排序方法是絕對最優(yōu)的。有的適用于 N 較大的情況，有的適用于 N 較小的情況，因此，在實用時需根據(jù)不同情況適當(dāng)選用，甚至可將多種方法結(jié)合起來使用。 三 、 小結(jié) 各種排序算法的時間復(fù)雜度和空間復(fù)雜度比較 排序法 最差時間分析 平均時間復(fù)雜度 穩(wěn)定度 空間復(fù)雜度 冒泡排序 O(n2) O(n2) 穩(wěn)定 O(1) 快速排序 O(n2) O(n*log2n) 不穩(wěn)定 O(log2n)~O(n) 選擇排序 O(n2) O(n2) 穩(wěn)定 O(1) 折半插入 排序 O(n2) O(n2) 穩(wěn)定 O(1) 插入排序 O(n2) O(n2) 穩(wěn)定 O(1) 堆排序 O(n*log2n) O(n*log2n) 不穩(wěn)定 O(1) 希爾排序 O O 不穩(wěn)定 O(1) 通過這次課程設(shè)計作業(yè)我 切實體會到了如何去形成一篇程序文檔，并且認識到了“程序＝數(shù)據(jù)結(jié)構(gòu)＋算法”。 我們感受最深的一點是：以前用 C 編程，只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術(shù)，只是憑單 純的意識和簡單的語句來堆砌出一段程序。但現(xiàn)在編程感覺完全不同了， 在編寫一個程序之前，自己能夠綜合考慮各種因素，首先選取自己需要的數(shù)據(jù)結(jié)構(gòu)，然后選定一種或幾種存儲結(jié)構(gòu)來具 體的決定后面的函數(shù)的主要風(fēng)格。最后在編寫每一個函數(shù)之前，可以仔細斟酌比對，挑選出最適合當(dāng)前狀況的算法。這樣，即使在完整的還沒有寫出來之前，自己心中已經(jīng)有了明確的原圖了。這樣無形中就提高了自己編寫的程序的質(zhì)量。我們還體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫程序的關(guān)鍵。這次實驗中我們也出現(xiàn)過一些錯誤。但我們經(jīng)過反復(fù)調(diào)試后，發(fā)現(xiàn)并做了修改，從而完成了此次課程設(shè)計。 在這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中，我此次的題目是各種 排序，排序?qū)嶋H上是編程設(shè)計中應(yīng)用比較廣泛的知識，通過本次設(shè)計，我對一些基本的內(nèi)部排序有了很好的理解和掌握，并且通過此次課程設(shè)計中的程序運行結(jié)果很好的理解了排序各種算法的穩(wěn)定性和時間復(fù)雜度，既鞏固了課堂上學(xué)到的排序理論，又為自己的編程增強了實踐。 總之， 在這次的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中，收獲還是蠻多的。也讓自己對數(shù)據(jù)結(jié)構(gòu)這門課程有了更好的認識 ，相信在越來越多的嘗試之后，自己會不斷進步不斷提高的。 第 38 頁 共 38 頁 四、 參考文獻 [1] 嚴蔚敏，吳偉民 .數(shù)據(jù)結(jié)構(gòu) . 北京： 清華大學(xué)出版社 ， 2022. [2] 嚴蔚敏、吳偉民、米寧 .數(shù)據(jù)結(jié)構(gòu)題集 . 北京： 清華大學(xué)出版社， 2022. [3] 譚浩強 . C 程序設(shè)計（第 4 版） 北京 ：清華大學(xué)出版社 ， 2022. [4] 何欽銘、馮雁、陳越 .數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 . 杭州：浙江大學(xué)出版社， 2022.