數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序綜合報(bào)告

1、數(shù)學(xué)與計(jì)算機(jī)學(xué)院 課程設(shè)計(jì)說明書 課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)-課程設(shè)計(jì) 課 程 代 碼: 8404181 題 目: 排序綜合 年級(jí)/專業(yè)/班: 2009 級(jí)軟件工程四班 學(xué) 生 姓 名: 學(xué) 號(hào): 開 始 時(shí) 間: 2011 年 06 月 20 日 完 成 時(shí) 間: 2011 年 07 月 03 日 課程設(shè)計(jì)成績(jī)： 學(xué)習(xí)態(tài)度及平 時(shí)成績(jī)（30） 技術(shù)水平與實(shí)際 能力（20） 創(chuàng)新 （5） 說明書撰寫質(zhì)量（45） 總 分 （100） 指導(dǎo)教師簽名： 年 月 摘摘 要要 排序（sorting）是計(jì)算機(jī)程序設(shè)計(jì)的一種重要操作，他的功能是將一組任意順序 數(shù)據(jù)元素（記錄） ，根據(jù)某一個(gè)（或幾個(gè)）關(guān)鍵字按

2、一定的順序重新排列成為有序的序 列。由于待排序的記錄數(shù)量不同，使得排序過程中涉及的存儲(chǔ)器的不同，可將排序方 法分為兩大類：一類是內(nèi)部排序，指的是待排序的記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn) 行的排序過程；另一類是外部排序，指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不 能容納全部記錄，在排序過程中尚需要對(duì)外存進(jìn)行訪問的排序過程。 內(nèi)部排序又分為：插入排序、快速排序、選擇排序、歸并排序和基數(shù)排序。其中 插入排序又分為：直接插入排序、其他插入排序和希爾排序；選擇排序分為：簡(jiǎn)單選 擇排序、樹形選擇排序和堆排序；基數(shù)排序分為：多關(guān)鍵字排序和鏈?zhǔn)交鶖?shù)排序。 本次課程設(shè)計(jì)就是內(nèi)部排序中的幾個(gè)常用排序方法。分析了排序

3、的實(shí)質(zhì)，排序的 應(yīng)用，排序的分類，利用 c 語(yǔ)言采用數(shù)組存儲(chǔ)結(jié)構(gòu)編程實(shí)現(xiàn)了本排序綜合系統(tǒng)，該系 統(tǒng)包含了幾種常見的排序方法，有直接插入排序、希爾排序、冒泡排序、非遞歸的快 速排序、遞歸的快速排序、簡(jiǎn)單排序、堆排序。 關(guān)鍵字關(guān)鍵字：內(nèi)部排序，外部排序，排序，重新排列，關(guān)鍵字 目目 錄錄 1 需求分析需求分析.1 1.1 任務(wù)與分析任務(wù)與分析 .1 1.2 功能模塊的劃分功能模塊的劃分 .1 1.2.1 輸入模塊.1 1.2.2 選擇排序方法模塊.1 1.2.3 輸出模塊.1 1.3 排序模塊分析排序模塊分析 .2 1.3.1 直接插入排序.2 1.3.2 希爾排序.2 1.3.3 冒泡排序.2

4、1.3.4 快速排序（遞歸和非遞歸）.2 1.3.5 簡(jiǎn)單排序.3 1.3.6 堆排序.3 1.4 系統(tǒng)需求分析規(guī)格說明書系統(tǒng)需求分析規(guī)格說明書 .3 2 開發(fā)及運(yùn)行平臺(tái)開發(fā)及運(yùn)行平臺(tái).4 2.1 windows操作系統(tǒng)操作系統(tǒng).4 2.2 vc+6.0.4 3 概要設(shè)計(jì)概要設(shè)計(jì).4 3.1 程序結(jié)構(gòu)框圖程序結(jié)構(gòu)框圖 .4 3.2 程序流程圖程序流程圖 .5 3.3 抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義 .5 3.4 各種操作函數(shù)：各種操作函數(shù)： .6 3.5 主函數(shù)主函數(shù) .6 4 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì).7 4.1 數(shù)據(jù)類型定義數(shù)據(jù)類型定義 .7 4.2 主要模塊內(nèi)部設(shè)計(jì)主要模塊內(nèi)部設(shè)計(jì) .7 4.

5、2.1 模塊 1 直接插入排序模塊設(shè)計(jì).7 4.2.2 模塊 2 希爾排序模塊設(shè)計(jì).7 4.2.3 模塊 3 冒泡排序模塊設(shè)計(jì).8 4.2.4 模塊 4 非遞歸快排模塊設(shè)計(jì).9 4.2.5 模塊 5 遞歸快排模塊設(shè)計(jì).10 4.2.6 模塊 6 簡(jiǎn)單排序模塊設(shè)計(jì).10 4.2.7 模塊 7 堆排序模塊設(shè)計(jì).10 5 調(diào)試分析調(diào)試分析.12 5.1 調(diào)試過程調(diào)試過程 .12 5.2 性能分析性能分析 .12 6 測(cè)試分析測(cè)試分析.13 6.1 測(cè)試用例測(cè)試用例 .13 6.2 測(cè)試結(jié)果測(cè)試結(jié)果 .13 7 結(jié)論結(jié)論.15 參考文獻(xiàn)參考文獻(xiàn).16 附附 錄錄.17 1 1 1 需需求求分分析析 1

6、.11.1 任務(wù)與分析任務(wù)與分析 任務(wù)： 機(jī)函數(shù)產(chǎn)生 n 個(gè)隨機(jī)整數(shù)（20000 以上） ，對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。 要求： 1)至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、 希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序） 。并把排序后的 結(jié)果保存在不同的文件中。 2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比） ， 找出其中兩種較快的方法。 分析： 前面分析了排序的種類以及過程，因此，本系統(tǒng)實(shí)現(xiàn)了幾種常用的排序方法， 包括：直接插入排序、希爾排序、冒泡排序、非遞歸的快速排序、遞歸的快速排 序、簡(jiǎn)單排序、堆排序。 1.21.2 功能模

7、塊的劃分功能模塊的劃分 1.2.11.2.1 輸入模塊輸入模塊 利用隨機(jī)函數(shù)產(chǎn)生 n 個(gè)數(shù)（20000 以上） ，產(chǎn)生的數(shù)據(jù)個(gè)數(shù)有用戶自己輸入。 1.2.21.2.2 選擇排序方法模塊選擇排序方法模塊 在菜單中通過鍵入相應(yīng)的選項(xiàng)編號(hào)來選擇采用何種算法排序，包括的排序算法有： 直接插入排序、希爾排序、冒泡排序、非遞歸的快速排序、遞歸的快速排序、簡(jiǎn)單排 序、堆排序。 1.2.31.2.3 輸出模塊輸出模塊 輸出排序前的，或者排序后的數(shù)據(jù)元素到屏幕上顯示，并且輸出一某一種算法排 序后的數(shù)據(jù)元素到文件中保存。 2 1.31.3 排序模塊分析排序模塊分析 1.3.11.3.1 直接插入排序直接插入排序

8、思路：設(shè)有一組關(guān)鍵字k1,k2,.,kn,排序開始變認(rèn)為 k1 是一個(gè)有序的序列, 讓 k2 插入到表長(zhǎng)為 1 的有序序列,使之成為一個(gè)表長(zhǎng)為 2 的有序序列, 讓 k3 插入到表 長(zhǎng)為 2 的有序序列,使之成為一個(gè)表長(zhǎng)為 3 的有序序列,依次類推,最后讓 kn 插入上述表 長(zhǎng)為 n-1 的有序序列,得到一個(gè)表長(zhǎng)為 n 的有序序列. 1.3.21.3.2 希爾排序希爾排序 思路：先取一個(gè)正整數(shù) d1(d1n),把全部記錄分成 d1 個(gè)組,所有距離為 d1 的倍數(shù)的 記錄看成是一組,然后在各組內(nèi)進(jìn)行插入排序;然后取 d2(d2=1),即所有記錄成為一個(gè)組為此.一般選 d1 約為 n/2,d2 為

9、 d1/2,.,di=1 1.3.31.3.3 冒泡排序冒泡排序 思路：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟： 首先比較第 1 個(gè)和第 2 個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第 2 個(gè)數(shù)和第 3 個(gè)數(shù)， 將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。 至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對(duì)數(shù)開始比較（因?yàn)?可能由于第 2 個(gè)數(shù)和第 3 個(gè)數(shù)的交換，使得第 1 個(gè)數(shù)不再小于第 2 個(gè)數(shù)） ，將小數(shù)放前， 大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的） ，第二趟結(jié)束， 在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)

10、（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)） 。如此下 去，重復(fù)以上過程，直至最終完成排序。用二重循環(huán)實(shí)現(xiàn)，外循環(huán)變量設(shè)為 i，內(nèi)循環(huán) 變量設(shè)為 j。外循環(huán)重復(fù) 9 次，內(nèi)循環(huán)依次重復(fù) 9，8，.，1 次。每次進(jìn)行比較的兩個(gè) 元素都是與內(nèi)循環(huán) j 有關(guān)的，它們可以分別用 aj和 aj+1標(biāo)識(shí)，i 的值依次為 1,2,.,9，對(duì)于每一個(gè) i, j 的值依次為 1,2,.10-i。 1.3.41.3.4 快速排序（遞歸和非遞歸）快速排序（遞歸和非遞歸） 思路:以第一個(gè)關(guān)鍵字 k1 為控制字，將k1、k2、.kn分成兩個(gè)子區(qū)，使左區(qū)的 有關(guān)鍵字小于等于 k1，右區(qū)所有關(guān)鍵字大于等于 k1，最后控制居兩個(gè)子區(qū)中間

11、的適 當(dāng)位置。在子區(qū)內(nèi)數(shù)據(jù)尚處于無序狀態(tài)。 將右區(qū)首、尾指針保存入棧，對(duì)左區(qū)進(jìn)行與第（1）步相類似的處理，又得到它的 3 左子區(qū)和右子區(qū)，控制字區(qū)中。 重復(fù)第（1） 、 （2）步，直到左區(qū)處理完畢。然后退棧對(duì)一個(gè)個(gè)子區(qū)進(jìn)行相類似的 處理，直到棧空 分區(qū)處理函數(shù) hoare( ) 思路：首先用兩個(gè)指針 i、j 分別指向首、尾兩個(gè)關(guān)鍵字，i=1，j=8。如對(duì) (46、56、14、43、95、10、19、72)。第一個(gè)關(guān)鍵字 46 作為控制字，該關(guān)鍵字所屬的 記錄另存儲(chǔ)在一個(gè) x 變量中。從文件右端元素 rj.key 開始與控制字 x.key 相比較，當(dāng) rj.key 大于等于 x.key 時(shí)，rj

12、不移動(dòng)，修改指針 j，j-，直到 rj.keyx.key，把記錄 rj移動(dòng)到文件左邊 i 所指向的位置;然后在文件左邊修改 i 指針,i+，讓 ri.key 與 x.key 相比較，當(dāng) ri.key 小于等于 x.key 時(shí)，ri不移動(dòng)，修改指針 i，i-，直到 ri. keyx.key, 把記錄 ri移動(dòng)到文件右邊 j 所指向的位置;然后在文件右邊修改 j 指針 j-。 重復(fù)上面的步驟. 1.3.51.3.5 簡(jiǎn)單排序簡(jiǎn)單排序 思路：在 n 個(gè)記錄中，用兩重循環(huán)，外層循環(huán) i 從第一個(gè)元素 a0開始至最后一個(gè) 元素 an-1，內(nèi)層循環(huán) j 從外層循環(huán)所值元素 ai的下一個(gè)元素 aj=ai+1

13、開始至最后一 個(gè)元素 an-1搜索，只要找到比 ai小的元素，便與 ai交換，如此重復(fù)執(zhí)行操作，當(dāng) 外層循環(huán)完畢后，全部記錄就排序完成了。 1.3.61.3.6 堆排序堆排序 思路：把 n 個(gè)記錄存于向量 r 之中，把它看成完全二叉樹，此時(shí)關(guān)鍵字序列不一 定滿足堆的關(guān)系。堆排序大體分為兩步處理： 初建堆，從堆的定義出發(fā)，當(dāng) i=1、2、 。 。 。 。 、2/n時(shí)應(yīng)滿足 ki=k2i 和 ki=k2i+1. 所以先取 i=n/2(它一定是第 n 個(gè)結(jié)點(diǎn)的雙親編號(hào)),將以 i 結(jié)點(diǎn)為根的子樹調(diào)整為堆，然 后令 i=i-1，將以不結(jié)點(diǎn)為根的子樹調(diào)整為堆。此時(shí)可能會(huì)反復(fù)調(diào)整某些結(jié)點(diǎn)，直到 i=1 為

14、止，堆初步建成。 堆排序，首先輸出堆頂元素（一般是最小值）,讓堆中最后一個(gè)元素上移到原堆頂 位置，然后恢復(fù)堆。因?yàn)榻?jīng)過第一步輸出堆頂元素的操作后，往往破壞了堆關(guān)系，所 以要恢復(fù)堆；重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的步驟。 1.41.4 系統(tǒng)需求分析規(guī)格說明書系統(tǒng)需求分析規(guī)格說明書 這是一個(gè)關(guān)于排序的綜合系統(tǒng)，該系統(tǒng)包含就平時(shí)記錄操作中比較常見的幾種排 序方法；其中包括：直接插入排序、希爾排序、冒泡排序、非遞歸的快速排序、遞歸 4 的快速排序、簡(jiǎn)單排序、堆排序。應(yīng)用該系統(tǒng)可以完成數(shù)據(jù)記錄的排序操作。對(duì)不同 的數(shù)據(jù)量、不同的數(shù)據(jù)結(jié)構(gòu)可以采用不同的排序方法。 2 2 開開發(fā)發(fā) 及及運(yùn)運(yùn)行行

15、平平臺(tái)臺(tái) 2.12.1 windowswindows 操作系統(tǒng)操作系統(tǒng) 2.22.2 vc+6.0vc+6.0 本系統(tǒng)在上述環(huán)境中設(shè)計(jì)實(shí)現(xiàn)，并且編譯通過，能正常運(yùn)行。 3 3 概概要要 設(shè)設(shè)計(jì)計(jì) 3.13.1 程序結(jié)構(gòu)框圖程序結(jié)構(gòu)框圖 排序綜合系統(tǒng) 退 出 非 遞 歸 快 排 函 數(shù) 冒 泡 排 序 函 數(shù) 堆 排 序 函 數(shù) 簡(jiǎn) 單 排 序 函 數(shù) 遞 歸 快 排 函 數(shù) 希 爾 排 序 函 數(shù) 直 接 插 入 排 序 函 數(shù) 產(chǎn) 生 隨 機(jī) 數(shù) 函 數(shù) 圖 1 程序結(jié)構(gòu)框圖 5 3.23.2 程序流程圖程序流程圖 開始 調(diào)用歡迎界面函 數(shù)startface(); 選擇操作項(xiàng) （第一次應(yīng)先產(chǎn)

16、生隨機(jī) 數(shù)） 退 出 非 遞 歸 快 排 冒 泡 排 序 堆 排 序 簡(jiǎn) 單 排 序 遞 歸 快 排 希 爾 排 序 直 接 插 入 排 序 產(chǎn) 生 隨 機(jī) 數(shù) 結(jié)束 保存排序后文件 圖 2 程序流程圖 3.33.3 抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義 adt sort 數(shù)據(jù)對(duì)象：d=隨機(jī)產(chǎn)生的 num（用戶輸入）個(gè)數(shù)據(jù)元素； 基本操作：int creat()；-產(chǎn)生隨機(jī)數(shù) void insert_sort(struct element a, int n)；-直接插入排序 void shell_sort(struct element a,int n)；-希爾排序 void bubble_sort

17、(struct element a,int n)；-冒泡排序 int hoare(struct element a,int l,int h)；-快排的分區(qū)處理 void quick_sort_1(struct element a,int n)；-非遞歸快排 void quick_sort_2(struct element a,int l,int h)；-遞歸快排 void jiandan_sort(struct element a,int n)；-簡(jiǎn)單排序 void heap(struct element a,int i,int m)；-堆調(diào)整 6 void heapsort(struct e

18、lement a,int n)；-堆排序 adt sort 3.43.4 各種操作函數(shù)：各種操作函數(shù)： （1）創(chuàng)建一個(gè)數(shù)組函數(shù)：int creat()； （2）輸出數(shù)組函數(shù)：void print(struct element a,int n)； （3）保存函數(shù)：void save(struct element asize,int n, char filename ) （4）直接插入排序函數(shù)：void insert_sort(struct element a, int n) （5）希爾排序函數(shù)：void shell(struct element a,int n)； （6）冒泡排序函數(shù)：void

19、bubble_sort(struct element a,int n)； （7）快速排序分區(qū)處理函數(shù)：int hoare(struct element a,int l,int h)； （8）非遞歸的快速排序函數(shù)：void quick_sort_1(struct element a,int n)； （9）遞歸的快速排序函數(shù)：oid quick_sort_2(struct element a,int l,int h)； （10）簡(jiǎn)單排序函數(shù)：void jiandan_sort(struct element a,int n)； （11）調(diào)整堆的函數(shù)：void heap(struct element

20、a,int i,int m)； （12）堆排序函數(shù)：void heapsort(struct element a,int n)； （13）時(shí)間函數(shù)：start = clock();end = clock(); 3.53.5 主函數(shù)主函數(shù) void main() 顯示菜單 while（1） 接受命令（選擇要執(zhí)行的操作） ； 處理命令； 輸出結(jié)果； 7 4 4 詳詳細(xì)細(xì)設(shè)設(shè)計(jì)計(jì) 4.14.1 數(shù)據(jù)類型定義數(shù)據(jù)類型定義 #define size 1000000 struct element int key; listsize; 4.24.2 主要模塊內(nèi)部設(shè)計(jì)主要模塊內(nèi)部設(shè)計(jì) 4.2.14.2.1 模

21、塊模塊 1 1 直接插入排序模塊設(shè)計(jì)直接插入排序模塊設(shè)計(jì) 模塊算法： void insert_sort(struct element a, int n) for(i=1; i=0 i-) / 元素后移一個(gè)位置 ,0 號(hào)位置作為監(jiān)視哨 ai=ai-1; k=n/2; / 步長(zhǎng) while(k=1) 8 for(i=k+1;ia0.key) j=j-k; aj+k=a0; k=k/2; / 更新步長(zhǎng) for(i=0;in;i+) / 元素前移一個(gè)位置 ai=ai+1; printf( 希爾排序完成!n); 4.2.34.2.3 模塊模塊 3 3 冒泡排序模塊設(shè)計(jì)冒泡排序模塊設(shè)計(jì) 模塊算法： voi

22、d bubble_sort(struct element a,int n) for(i = 0;i n ; i+) flag=0; / flag 初始化，flag- 標(biāo)志變量，判斷是否需要循環(huán) for(j = 0;j aj+1.key) / 滿足條件交換元素 ai aj; flag=1; if(flag=0) break; printf( 冒泡排序完成!n); 9 4.2.44.2.4 模塊模塊 4 4 非遞歸快排模塊設(shè)計(jì)非遞歸快排模塊設(shè)計(jì) 模塊算法： int hoare(struct element a,int l,int h)/分區(qū)處理函數(shù) i=l;j=h;x=ai; /初始化 do wh

23、ile(i=x.key) /從后向前搜索第一個(gè)小于 x 的元素 j-; if(ij) ai=aj;i+; while(ij) if(ij) / ij 則將 ai復(fù)制給 aj，j 向前移動(dòng)一個(gè)位置 aj=ai; j-; while(ij); ai=x; return(i); /非遞歸的快速排序/ void quick_sort_1(struct element a,int n) /非遞歸的快速排序 int s202; l=0;h=n-1;tag=1;top=0; /初始化 do while(lh) i=hoare(a,l,h); / 分區(qū)處理 top+; stop0=i+1; stop1=h;

24、h=h-1; if(top=0) tag=0; / 處理完標(biāo)志 10 else l=stop0; h=stop1; top-; while(tag=1); printf( 非遞歸快排完成!n); 4.2.54.2.5 模塊模塊 5 5 遞歸快排模塊設(shè)計(jì)遞歸快排模塊設(shè)計(jì) 模塊算法： void quick_sort_2(struct element a,int l,int h) /遞歸的快速排序 if(lh) i=hoare(a,l,h); /劃為兩個(gè)區(qū) quick_sort_2(a,l,i-1); /對(duì)左分區(qū)快速排序 quick_sort_2(a,i+1,h); /對(duì)右分區(qū)快速排序 4.2.64

25、.2.6 模塊模塊 6 6 簡(jiǎn)單排序模塊設(shè)計(jì)簡(jiǎn)單排序模塊設(shè)計(jì) 模塊算法： void jiandan_sort(struct element a,int n) for(i = 0;i n; i+ ) for(j = i + 1;j aj.key) /滿足條件，交換元素 ai aj; printf( 簡(jiǎn)單排序完成!n); 4.2.74.2.7 模塊模塊 7 7 堆排序模塊設(shè)計(jì)堆排序模塊設(shè)計(jì) 模塊算法 /調(diào)整堆的函數(shù) void heap(struct element a,int i,int m) 11 /*i 是根結(jié)點(diǎn)編號(hào),m 是以 i 為根的子樹的最后一個(gè)結(jié)點(diǎn)編號(hào)*/ x=ai; /保存記錄內(nèi)容

26、j=2*i; /j 為左孩子編號(hào) while(j=m) if(jaj+1.key) /當(dāng)結(jié)點(diǎn) i 有左,右兩個(gè)孩子時(shí),j 取關(guān)鍵較小 的孩子編號(hào) j+; if(aj.keym,以便結(jié)束循環(huán) ai=x; /堆排序的主體函數(shù) void heapsort(struct element a,int n) for(i=n;i0;i-) /全部元素后移一位 ai=ai-1; for(i=n/2;i=1;i-) heap(a,i,n); /堆調(diào)整 for(v=n;v=2;v-) a1 av; /堆頂堆尾元素交換 heap(a,1,v-1); /這次比上次少處理一個(gè)記錄 for(i=0;in;i+) /元素前

27、移一位 ai=ai+1; for(i=0;in/2;i+) /交換元素 ai an-i-1; printf( 堆排序完成!n); 12 5 5 調(diào)調(diào)試試分分析析 5.15.1 調(diào)試過程調(diào)試過程 根據(jù)編譯的報(bào)錯(cuò)和告警提示，改正程序中的語(yǔ)法和語(yǔ)義錯(cuò)誤，是程序能運(yùn)行。在 根據(jù)測(cè)試分析算法的正確與否調(diào)試程序中的排序算法，使每種排序算法能正確執(zhí)行操 作。 5.25.2 性能分析性能分析 5.2.1、insertion_sort 排序算法分析： 該算法的時(shí)間復(fù)雜度為 o(n*n).直接插入排序是穩(wěn)定的排序方法。當(dāng) n 值較小時(shí)， n 和 n2的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度 o(n)和最壞時(shí)間

28、復(fù)雜度 0(n2)差 別不大。 5.2.2、shell 排序算法分析： shell 排序算法的時(shí)間復(fù)雜度分析比較復(fù)雜，實(shí)際所需的時(shí)間取決于各次排序時(shí)增 量的個(gè)數(shù)和增量的取值。當(dāng) n 較大時(shí)，比較和移動(dòng)的次數(shù)約在 nl.25 到 1.6n1.25 之間。 由于 shell 排序算法是按增量分組進(jìn)行的排序，所以 shell 排序算法是一種不穩(wěn)定的 排序算法。 5.2.3、bubble 排序算法分析： 這是最原始，也是眾所周知的最慢的算法了。它的名字的由來是它的工作看起來 想冒泡。該算法的時(shí)間復(fù)雜度為：o(n*n)。 5.2.4、quick 排序算法分析： 快速排序主體算法時(shí)間運(yùn)算約為 o(log2

29、n),劃分子區(qū)函數(shù)運(yùn)算量約為 o(n)，所總 時(shí)復(fù)雜度為 o(nlog2n). 因?yàn)榭焖倥判虻挠涗浺苿?dòng)次數(shù)不大于比較的次數(shù)，所以快速排 序的最壞時(shí)間復(fù)雜度應(yīng)為 0(n2)，最好時(shí)間復(fù)雜度為 o(nlgn)。 5.3.5、簡(jiǎn)單排序算法分析： 從算法中用了兩重循環(huán)可以看出，該算法的時(shí)間復(fù)雜度為：o（n*n） 。 5.3.6、heapsort 排序算法分析： 13 堆排序中 heap 算法的時(shí)間復(fù)雜度與堆所對(duì)應(yīng)的完全二叉樹的深度log2n+1 相關(guān)， 而 heapsort 中對(duì) heap 的調(diào)用數(shù)量級(jí)為 n，所以整個(gè)堆排序的時(shí)間復(fù)雜度為 o(nlog2n)。 堆排序是不穩(wěn)定的。 6 6 測(cè)測(cè)試試 分

30、分析析 6.16.1 測(cè)試用例測(cè)試用例 不需要人工輸入任何測(cè)試數(shù)據(jù)，由系統(tǒng)隨機(jī)產(chǎn)生數(shù)據(jù)，產(chǎn)生的個(gè)數(shù)由用戶輸入。 用隨機(jī)函數(shù)產(chǎn)生的 20 個(gè)隨機(jī)作為測(cè)試用例： 圖 3 隨機(jī)函數(shù)產(chǎn)生隨機(jī)數(shù)截圖 6.26.2 測(cè)試結(jié)果測(cè)試結(jié)果 圖 4 直接插入排序截圖 14 圖 5 希爾排序截圖 圖 6 冒泡排序截圖 圖 7 非遞歸快排截圖 圖 8 遞歸快排截圖 圖 9 簡(jiǎn)單排序截圖 15 圖 10 堆排序截圖 7 7 結(jié)結(jié)論論 通過這次課程設(shè)計(jì)的學(xué)習(xí)讓我學(xué)會(huì)了許多。讓我對(duì)我們的專業(yè)知識(shí)有了很大 理解！ 我對(duì)專業(yè)的課程有了初步的認(rèn)識(shí)。 在這次課程設(shè)計(jì)中，獨(dú)立完成了在數(shù)組存儲(chǔ)結(jié)構(gòu)下的每種排序算法。排序算法共 有六個(gè)：

31、插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序。同時(shí)也實(shí) 現(xiàn)了隨機(jī)數(shù)的生成。并把排序后的結(jié)果保存在不同的文件中。雖然在算法完成的過程 中也在網(wǎng)上查閱了一些資料，但對(duì)這次課程設(shè)計(jì)的成果還是非常滿意的。 這次的課程設(shè)計(jì)還有很多不足之處，如數(shù)組存儲(chǔ)結(jié)構(gòu)中的堆排序算法，當(dāng)排序個(gè) 數(shù)過多時(shí)，就會(huì)等待很長(zhǎng)時(shí)間。可能是調(diào)用的函數(shù)過多的原因造成的，但排序是正確 的。由于時(shí)間限制，只在課程設(shè)計(jì)快結(jié)束時(shí)完成了產(chǎn)生隨機(jī)文件這部分，我想以后有 時(shí)間再來完成它。 同時(shí)在完成這個(gè)課程設(shè)計(jì)后，我也學(xué)到了很多知識(shí)，并能熟練的掌握他們了。熟 練的撐握了 c 語(yǔ)言的文件讀寫操作。撐握了每種排序算法的基本思想，并學(xué)會(huì)了編

32、寫 程序的一般步驟：思考問題，寫出解決方案，寫出偽代碼，完成代碼，調(diào)試程序。不 像以前那樣開始就直接寫代碼。 所以，這次的課程設(shè)計(jì)我學(xué)會(huì)了很多，不光讓我認(rèn)識(shí)了本專業(yè)知識(shí)，還讓我學(xué)了 一定的心境！那就是做事情的時(shí)候即使不會(huì)做也不能慌張，要慢慢放下心來，不要光 想自己怎么、怎么不會(huì)了！不要去想不會(huì)，而是冷下心來慢慢思考、思考。這樣你就 會(huì)有了思慮的。 16 參參考考文文獻(xiàn)獻(xiàn) 1 嚴(yán)蔚敏等編著. 數(shù)據(jù)結(jié)構(gòu)（c 語(yǔ)言版）. 北京：清華大學(xué)出版社，2003 2 嚴(yán)蔚敏等編著. 數(shù)據(jù)結(jié)構(gòu)題集（c 語(yǔ)言版）. 北京：清華大學(xué)出版社，2003 3 李春葆等編著. 數(shù)據(jù)結(jié)構(gòu)教程（c 語(yǔ)言版）. 北京：清華大學(xué)出

33、版社，2006 4 朱立華等編著. c 語(yǔ)言程序設(shè)計(jì). 北京：人民郵電出版社，2009 17 附附 錄錄 附錄 1 源程序清單 #include #include #include #define size 1000000 / 定義數(shù)據(jù)類型結(jié)構(gòu)體 / /關(guān)鍵字定義在結(jié)構(gòu)體中，方便以后的代碼重用 struct element int key; listsize; /創(chuàng)建一個(gè)數(shù)組/ int creat() int i; / i- 循環(huán)控制 int num; / num- 記錄元素的個(gè)數(shù) printf( 請(qǐng)輸入元素個(gè)數(shù):); scanf(%d, if(num999999) printf(輸入超界!n

34、); return 0; for( i = 0;i num; i+ ) / 循環(huán)產(chǎn)生 num 個(gè)隨機(jī)數(shù) listi.key = rand() % 10000; return(num); /輸出數(shù)組/ void print(struct element a,int n) int i; for(i=0;in;i+) / 循環(huán)輸出 printf(%5d,ai .key); printf(n); /保存到文件/ void save(struct element a,int n, char filename ) int m_wr=0; / 寫入 txt 文件變量 file *fp; if ( ( fp

35、= fopen ( filename, w ) ) = null ) printf(file writer errorn); for (int m=0; mn; m+ ) m_wr = am.key; fprintf ( fp, %d , m_wr ); / 寫入 txt 中 fclose ( fp ); 18 / 直接插入排序/ void insert_sort(struct element a, int n) int i, j; / 循環(huán)控制變量 struct element next; / 臨時(shí)存放空間 for(i=1; i=0 i-) / 元素后移一個(gè)位置 ,0 號(hào)位置作為監(jiān)視哨 ai

36、=ai-1; k=n/2; / 步長(zhǎng) while(k=1) for(i=k+1;ia0.key) j=j-k; aj+k=a0; k=k/2; for(i=0;in;i+) / 元素前移一個(gè)位置 ai=ai+1; printf( 希爾排序完成!n); /冒泡排序/ void bubble_sort(struct element a,int n) int i,j,flag; / flag- 標(biāo)志變量，判斷是否需要循環(huán) struct element temp; for(i = 0;i n ; i+) flag=0; / 初始化 for(j = 0;j aj+1.key) / 滿足條件交換元素 19

37、 temp=aj; aj=aj+1; aj+1=temp; flag=1; if(flag=0) break; printf( 冒泡排序完成!n); /快速排序/ int hoare(struct element a,int l,int h)/分區(qū)處理函數(shù) int i,j; struct element x; i=l; j=h; x=ai; do while(i=x.key) /從后向前搜索第一個(gè)小于 x 的元素 j-; if(ij) ai=aj; i+; while(ij) if(ij) / ij 則將 ai復(fù)制給 aj，j 向前移動(dòng)一個(gè)位置 aj=ai; j-; while(ij); ai

38、=x; return(i); /非遞歸的快速排序/ void quick_sort_1(struct element a,int n) /非遞歸的快速排序 int i,l,h,tag,top; int s202; l=0;h=n-1;tag=1;top=0; do while(lh) i=hoare(a,l,h); / 分區(qū)處理 top+; stop0=i+1; 20 stop1=h; h=h-1; if(top=0) tag=0; / 處理完標(biāo)志 else l=stop0; h=stop1; top-; while(tag=1); printf( 非遞歸快排完成!n); /遞歸的快速排序/

39、void quick_sort_2(struct element a,int l,int h) /遞歸的快速排序 int i; if(lh) i=hoare(a,l,h); /劃為兩個(gè)區(qū) quick_sort_2(a,l,i-1); /對(duì)左分區(qū)快速排序 quick_sort_2(a,i+1,h); /對(duì)右分區(qū)快速排序 /簡(jiǎn)單排序函數(shù)/ void jiandan_sort(struct element a,int n) int i,j; /循環(huán)控制變量 struct element temp; /臨時(shí)變量 for(i = 0;i n; i+ ) for(j = i + 1;j aj.key) /

40、滿足條件，交換元素 temp=ai; ai=aj; aj=temp; printf( 簡(jiǎn)單排序完成!n); /堆排序函數(shù)/ /調(diào)整堆的函數(shù) void heap(struct element a,int i,int m) /*i 是根結(jié)點(diǎn)編號(hào),m 是以 i 為根的子樹的最后一個(gè)結(jié)點(diǎn)編號(hào)*/ struct element x; int j; x=ai; /保存記錄內(nèi)容 21 j=2*i; /j 為左孩子編號(hào) while(j=m) if(jaj+1.key) /當(dāng)結(jié)點(diǎn) i 有左,右兩個(gè)孩子時(shí),j 取關(guān)鍵較小的孩子編號(hào) j+; if(aj.keym,以便結(jié)束循環(huán) ai=x; /堆排序的主體函數(shù) voi

41、d heapsort(struct element a,int n) int i,v; /循環(huán)控制變量 struct element x; /臨時(shí)變量 for(i=n;i0;i-) /元素后移一位 ai=ai-1; for(i=n/2;i=1;i-) heap(a,i,n); /堆調(diào)整 for(v=n;v=2;v-) x=a1; /堆頂堆尾元素交換 a1=av; av=x; heap(a,1,v-1); /這次比上次少處理一個(gè)記錄 for(i=0;in;i+) /元素前移一位 ai=ai+1; for(i=0;in/2;i+) /交換元素 x=ai; ai=an-i-1; an-i-1=x;

42、printf( 堆排序完成!n); / 歡迎界面函數(shù) / void startface() system(color 0a); /設(shè)置屏幕顯示的前景色、背景色 system(cls); /清屏 printf(nnnnn); printf( * 22 n); printf( * * n); printf( * 歡迎使用綜合排序系統(tǒng) * n); printf( * * n); printf( * n); printf(nnnnnnnnnn); system(pause); /暫停 / 菜單函數(shù) / void menu() system(cls); /清屏 printf(ntt* 主菜單 *n);

43、printf(tt| |n); printf(tt| 1-生成隨機(jī)排序元素 |n); printf(tt| 2-直接插入排序 |n); printf(tt| 3-希爾排序 |n); printf(tt| 4-冒泡排序 |n); printf(tt| 5-非遞歸的快速排序 |n); printf(tt| 6-遞歸的快速排序 |n); printf(tt| 7-簡(jiǎn)單排序 |n); printf(tt| 8-堆排序 |n); printf(tt| 0-退出 |n); printf(tt| |n); printf(n); void main() int num,c; / num- 記錄個(gè)數(shù)， c- 操作選項(xiàng) int flag=0; /標(biāo)志 clock_t start, end; / 計(jì)時(shí)變量 / 文件名數(shù)組 / char file130 = 直接插入排序.txt; char file230 = 希爾排序.txt; char file330 = 冒泡排序.txt; char file430 = 非遞歸的快速排序.txt; char file530 = 遞歸的快速排序.txt; char file630 = 簡(jiǎn)單排序.txt; char file730 = 堆排序.txt; startface(); menu(); 23 while(1) pri