排序算法實(shí)現(xiàn)4

1、河南工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)成果報(bào)告排序算法實(shí)現(xiàn)2014年12月29日3程序清單#include#include#define num 40ttdefine TRUE 1ttdefine FALSE 0void InsertSort(long a, int length);void BlnsertSort(long a, long length);void ShellSort(long a, int dlta, int t);void BubbleSort(long a, int length);void Quicksort(long a, int low, int length);vo

2、id SelectSort(long a, int length);void Shelllnsert(long a, int length, int dk); int Partition(long a, int low, int high);int SelectMinKey(long a, int length,int i); void print(long a, int n);int main () int i=0;int dlta3 = 5, 3, 1;long anum;for(i=0;inum;i+)ai=rand()%100; printf(直接插入所排序列為：n)； InsertS

3、ort(a, num);print (a, num);printf(n);printf(折半插入所排序列為：n)；BlnsertSort(a, num);print (a, num);printf(n);printf(希爾排序所排序列為：n)；ShellSort (a, dlta, 3);print (a, num);printf(n);printf(起泡排序所排序列為：n)；BubbleSort(a, num);print (a, num);printf (n);printf(快速排序所排序列為:n)；Quicksort(a, 1, num);print(a, num);printf(n);

4、printf(簡單項(xiàng)選擇擇所排序列為：n)；SelectSort(a, num);print (a, num);printf(n);return 0;)直接插入排序void InsertSort(long a, int length)對順序表做直接插入排序int i, j;for(i=2;ilength;+i)if(aiai-l)a0=ai;ai=ai-l;for(j=i-2;a0aj j) aj+l=aj;aj+l=a0;折半插入排序void BlnsertSort(long a, long length) 對順序表做折半插入排序 int i, j, mid, low, high; for

5、(i=2;ilength;+i) a0=ai;low=l;high=i-l;while (low二high) mid= (low+high)/2;if (a0=high+1;j) aj+l=aj;復(fù)制為哨兵記錄后移插入到正確位置復(fù)制為哨兵折半查找有序插入位置折半插入點(diǎn)在低半?yún)^(qū)插入點(diǎn)在高半?yún)^(qū)插入ahigh+l=a0; 希爾排序void Shelllnsert(long a, int length,int dk)對順序表做一趟希爾插入排序int i, j;for(i=dk+l;ilength;+i)if(ai0&a0aj;j-=dk)aj4-dk=aj;記錄后移，查找插入位置aj+dk=a0 ;

6、插入)void ShellSort(long a, int dlta, int t) 對順序表做希爾排序int k;for(k=0;k=l&change;-i) change=FALSE;for(j=0;jaj+l) n=aj;aj=aj+l;aj+l=n;change二TRUE;快速排序int Partition (long a., int low, int high).int pivotkey;a0=alow;用子表第一個(gè)記錄作樞紐記錄pivotkey=alow;樞紐記錄關(guān)鍵字while(lowhigh) while(1ow=pivotkey)一high;alow=ahigh;將比樞紐記錄

7、小的記錄移到低端while(1owh i gh&a1ow=pivotkey)+low;ahigh=alow ;將比樞紐記錄大的記錄移到高端alow=a0;樞紐記錄到位return low;返回樞紐位置)void Quicksort(long a, int low, int length) (int pivotloc, high;high=length;if(lowhigh) pivotloc=Partition(a, low, high);Quicksort (a, low, pivotloc-1); 對低子表遞歸排序Quicksort (a, pivotloc+1, high) ; 對高子表

8、遞歸排序簡單項(xiàng)選擇擇排序int SelectMinKey (long a, int length,int i)選擇最小記錄int n;for(n=i+1;nan)i=n;return i;)void SelectSort(long a, int length)對順序表做簡單項(xiàng)選擇擇排序int i, j, x;for (i=l;ilength;+i)j二SelectMinKey(a, length, i);if (i !=j)與第i個(gè)記錄交換 x=ai;ai=aj;aj=x;void print (long aLJ, int n)輸出由小到大排列好的序列int i;for (i=l; in; i

9、+) 每行20個(gè)數(shù)字對齊 printf(2d ，ai);if(i%20=0)printf (n);4測試4.1測試數(shù)據(jù)程序調(diào)用rand ()函數(shù)產(chǎn)生的隨機(jī)數(shù)據(jù)。4. 2測試結(jié)果分析在程序編譯運(yùn)行前首先確定序列數(shù)量num值，主函數(shù)調(diào)用rand()函數(shù)產(chǎn)生隨機(jī)數(shù)。依次調(diào)用各算法，運(yùn)行結(jié)果如下列圖:圖4. 2運(yùn)行結(jié)果105總結(jié)“熟能生巧”這句話在各行各業(yè)都很適用，尤其是軟件工程這門課程中。“大 ?！辈皇钦f出來的，只有多寫多練多想才能成為人們口中說道稱羨的“大?！?。 在這次課程設(shè)計(jì)中，充分認(rèn)識了自己并發(fā)現(xiàn)了自己的缺乏一一專業(yè)知識掌握不太 牢固，想法單一，缺少動(dòng)手能力。認(rèn)識到自己的缺點(diǎn)，就要努力克服改正

10、?！睂W(xué) 而不思那么罔，思而不學(xué)那么殆”。想要學(xué)好本專業(yè)，就要把“心腦手”結(jié)合在一起。這次實(shí)踐，也使我真正體會(huì)到了算法是程序設(shè)計(jì)的精髓，只有洞悉算法，才 能編寫好一個(gè)稱之為WONDERFUL的程序。最后，要感謝老師和同學(xué)們的幫助。如果沒有老師的指導(dǎo)和同學(xué)們的幫助， 我就無法完成程序設(shè)計(jì)任務(wù)，可見團(tuán)隊(duì)的力量遠(yuǎn)大于個(gè)人力量。所以我們在單獨(dú) 完成任務(wù)的同時(shí)，也要有團(tuán)結(jié)別人的精神。參考文獻(xiàn)(1)數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏清華大學(xué)出版社2002(2)數(shù)據(jù)結(jié)構(gòu)-C語言描述王路群中國水利水電出版社2007(3)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程(C語言版)王國鈞清華大學(xué)出版社2009(4)數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏，吳偉民編 清華大學(xué)

11、出版社200211題目排序算法實(shí)現(xiàn)考核工程考核內(nèi)容得分平時(shí)考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、 基本操作技能、知識應(yīng)用能力、獲取知識能力系統(tǒng)設(shè)計(jì)（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實(shí)現(xiàn)系統(tǒng)的各個(gè)功能模塊，并完成調(diào)試回答下列問題（15分）回答老師針對課程設(shè)計(jì)提出的問題課程設(shè)計(jì)報(bào)告撰寫（10分）嚴(yán)格按照規(guī)范要求完成課程設(shè)計(jì)報(bào)告源代碼（5分）按照規(guī)范要求完成課程設(shè)計(jì)源代碼的排版總評成績指導(dǎo)教師評語：日期：年 月日 TOC o 1-5 h z 1課程設(shè)計(jì)目標(biāo)與任務(wù)11.1設(shè)計(jì)目標(biāo)12設(shè)計(jì)任務(wù)1 HYPERLINK l bookmark14 o Current Document

12、1.3設(shè)計(jì)工程1 HYPERLINK l bookmark16 o Current Document 1.4所需工具12分析與設(shè)計(jì)21實(shí)驗(yàn)原理2 HYPERLINK l bookmark21 o Current Document 2存儲結(jié)構(gòu)設(shè)計(jì)3 HYPERLINK l bookmark23 o Current Document 3算法描述3 HYPERLINK l bookmark25 o Current Document 程序流程圖6 HYPERLINK l bookmark27 o Current Document 測試程序說明6 HYPERLINK l bookmark0 o Curr

13、ent Document 3程序清單74測試104.1測試數(shù)據(jù)10 HYPERLINK l bookmark5 o Current Document 4. 2測試結(jié)果分析10 HYPERLINK l bookmark7 o Current Document 5總結(jié)11 HYPERLINK l bookmark9 o Current Document 參考文獻(xiàn)111課程設(shè)計(jì)目標(biāo)與任務(wù)設(shè)計(jì)目標(biāo)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程后的實(shí)踐教學(xué)環(huán)節(jié)。該實(shí)踐教學(xué)是 軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析、總體結(jié)構(gòu)設(shè)計(jì)用戶界面設(shè)計(jì)、程序設(shè)計(jì)基 本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力，培養(yǎng)科學(xué)的軟件工

14、作 方法。通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，能力得到鍛煉：(1)能根據(jù)實(shí)際問題具體情況結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和算法，正 確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理選擇相應(yīng)存儲結(jié)構(gòu)，設(shè)計(jì)出解決問題的有效算法;(2)通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)算法的正確性，學(xué)會(huì)有效利用基本調(diào)試 方法，迅速找出程序代碼中的錯(cuò)誤并且修改，培養(yǎng)算法分析能力。分析所設(shè)計(jì)算 法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平；(3)盡可能借助語言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖 形方式顯示出來,將復(fù)雜的運(yùn)行過程以動(dòng)態(tài)方式顯示出來，獲得算法的直觀感受。 1. 2設(shè)計(jì)任務(wù)根據(jù)提供的實(shí)習(xí)題目，認(rèn)真完成軟件設(shè)計(jì)的全部過程，并以最終軟件設(shè)計(jì)

15、成 果來證明其獨(dú)立完成實(shí)際任務(wù)的能力。從而，反映出理解和運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法 的水平和能力，最后完成軟件設(shè)計(jì)和程序調(diào)試并提交課程設(shè)計(jì)報(bào)告書，報(bào)告書中 包含設(shè)計(jì)的算法及局部程序代碼。1.3設(shè)計(jì)工程設(shè)計(jì)排序相關(guān)函數(shù)庫，以便在程序設(shè)計(jì)中調(diào)用，要求設(shè)計(jì)程序產(chǎn)生20000 個(gè)隨機(jī)數(shù)，完成下面功能：(1)對這些數(shù)分別進(jìn)行直接插入排序、折半插入排序、希爾排序、起泡排 序、快速排序、簡單項(xiàng)選擇擇排序、堆排序、2-路歸并排序，并把排序結(jié)果進(jìn)行保存;(2)最好能借助語言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖 形方式顯示出來，將復(fù)雜的運(yùn)行過程以動(dòng)態(tài)方式顯示出來；(3)給出假設(shè)干例程，演示通過調(diào)用自己所縮寫程序

16、來實(shí)現(xiàn)相關(guān)問題的求解。4所需工具PC機(jī)、Win7、VC6. 0語言編輯。2分析與設(shè)計(jì)2.1實(shí)驗(yàn)原理直接插入排序：在含有iT個(gè)記錄的有序子序列al. i-1中插入一個(gè)記錄ai 后，變成含有i個(gè)記錄的有序子序列rlX.i;為了在查找插入位置的過程中避 免數(shù)組下標(biāo)出界，在r0處設(shè)置監(jiān)視哨。在自i-l起往前搜索的過程中，可以 同時(shí)后移記錄。整個(gè)排序過程為進(jìn)行nT趟插入，時(shí)間復(fù)雜度為OG?)。折半插入排序：折半插入排序是在直接插入排序的基礎(chǔ)上進(jìn)行改進(jìn)，操作上利用 “折半查找”來實(shí)現(xiàn)。從時(shí)間上比擬，折半插入排序僅減少了關(guān)鍵字間的比擬次 數(shù)，而記錄的移動(dòng)次數(shù)不變。因此，折半插入排序的時(shí)間復(fù)雜度仍為0 (n2

17、) o希爾排序：希爾排序又稱“縮小增量排序”，也是一種插入排序類的方法。先將 整個(gè)待排記錄序列分割成為假設(shè)干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的 記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。子序列構(gòu)成不是簡 單地“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。時(shí)間復(fù)雜 度為 0 (n3/2) o冒泡排序：第i趟冒泡排序是從al到an-i+l依次比擬相鄰兩個(gè)記錄的關(guān)鍵 字，并在“逆序”時(shí)交換相鄰記錄，其結(jié)果是這n-i+l個(gè)記錄中關(guān)鍵字最大的記 錄被交換到第n-i+1的位置上。假設(shè)初始序列為“正序”序列，那么只需進(jìn)行一趟排 序，在排序過程中進(jìn)行nT次關(guān)鍵字間的比擬，且不移

18、動(dòng)記錄；反之，假設(shè)初始序 列為“逆序”序列，那么需進(jìn)行nT趟排序。時(shí)間復(fù)雜度為0(1?)?？焖倥判颍涸诖判虻男蛄兄校紫热稳∫粋€(gè)記錄作為樞軸，然后將關(guān)鍵字較它 小的記錄都安置在它的位置之前，將所有關(guān)鍵字較它的小的記錄都安置在它的位 置之前，所有比它大的記錄都安置在它的位置之后。附設(shè)兩個(gè)指針low和high, 初始值分別為low、high,設(shè)樞軸記錄關(guān)鍵字為pivokey,先將樞軸記錄暫存在 a0的位置上，排序過程只作allow或ahigh的單向移動(dòng)，直至一趟排序結(jié)束 后再將樞軸記錄移至正確位置上。時(shí)間復(fù)雜度為0(/)。2簡單項(xiàng)選擇擇排序：每一趟選擇排序從n-i+l個(gè)記錄中選出關(guān)鍵字最小的記錄

19、，并和 第i (l=i=n)個(gè)記錄交換。令i從1至nT,進(jìn)行nT趟選擇操作。時(shí)間復(fù)雜度 為 0 (n2) o2存儲結(jié)構(gòu)設(shè)計(jì)順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，線性表長度可變，且所需最大存 儲空間隨問題不同而不同。在該程序中數(shù)組元素是調(diào)用rand()函數(shù)隨機(jī)存取， 因此選用順序存儲結(jié)構(gòu)。在這種存儲結(jié)構(gòu)中，容易實(shí)現(xiàn)數(shù)組的某些操作。缺點(diǎn)是 在移動(dòng)元素上耗費(fèi)時(shí)間。3算法描述直接插入排序：void InsertSort ( elem R , int n) 對記錄序列RL.n作直接插入排序。for ( i=2; i=n; +i )R0 = Ri;/復(fù)制為監(jiān)視哨for ( j=i-l; R0 Rj ; j

20、 )Rj+U = Rj ；/ 記錄后移Rj+U = REO; /插入到正確位置 / InsertSort折半插入排序：void BlnsertSort (elem R , int n)/對記錄序列RL.n作折半插入排序。for ( i=2; i=n; +i )(R0= Ri:/ 將 Ri暫存到 R0low = 1; high = i-l;while ( low = high)/在Rlow. . high中折半查找插入的位置m = (low+high)/2;/ 折半if (R0 =high+l; j )Rj+1= Rj; / 記錄后移3Rhigh+1 = R0 ; / 插入 / BlnsertS

21、ort希爾排序：void Shelllnsert ( elem R , int dk ) /對待排序列R作一趟希爾插入排序 for ( i=dk+l; i=n; +i )if ( Ri Ri-dk)void ShellSort (elem R , int d , int t) 按增量序列d 0t-1對順序表L作希爾排序。for ( k=0; k0 & R01)(for ( j = 1; j i; j+ )if (R j+1 R j )(Swap(R j , R j+1 ); /if / while / BubbleSort快速排序：int Partition (Elem R, int low, int high)(/交換記錄子序列Rlow.high中的記錄，使樞軸記錄到位，并返回其所/在位置，此時(shí)，在它之前(后)的記錄均不大(小)于它R0=R