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

1、河南工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)成果報(bào)告排序算法實(shí)現(xiàn)2014年12月29日2.4程序流程圖開始開始顯示菜單直接插入排序輸入序號(hào)V折半插入排序簡(jiǎn)單項(xiàng)選擇擇排序按輸入序號(hào)輸出結(jié)果結(jié)束圖1-2程序執(zhí)行流程圖開始執(zhí)行后，會(huì)出現(xiàn)提示語句，提示6分別代表6種排序方法，對(duì)于生成 的數(shù)組，點(diǎn)擊1-6任意數(shù)字，調(diào)用相應(yīng)的排序方法進(jìn)行排序。輸出結(jié)果后，按任 意鍵結(jié)束。2. 5程序測(cè)試說明主函數(shù)會(huì)調(diào)用rand()方法，隨機(jī)產(chǎn)生指定數(shù)目數(shù)值。并將數(shù)值賦予指定數(shù) 組，通過提示語句輸入16數(shù)值，16分別代表不同的排序方式，當(dāng)輸入數(shù)字 1時(shí)，通過switch語句，將執(zhí)行直接插入排序函數(shù)，然后通過輸出函數(shù)，輸出 所需結(jié)構(gòu)。

2、3程序清單#include#include#includettdefine MAXE 20000typedef int KeyType;typedef struct/*記錄類型*/(KeyType key;/*關(guān)鍵字項(xiàng)*/InfoType data;/*其他數(shù)據(jù)項(xiàng)，類型為 InfoTypeV RecType;void InsertSort(RecType R, int length);直接插入排序void BlnsertSort (RecType R, int low, int high, int length);折半插入排序 void ShellSort (RecType R, int n)

3、;希爾排序 void bubble_sort(RecType R, int length);起泡排序 int FindPos(RecType R, int low, int high);void Quicksort(RecType R,int low, int high);int SelectMinKey(RecType R, int i, int length);void SelectSort (RecType R, int length);簡(jiǎn)單項(xiàng)選擇擇排序void showSort (RecType R);快速排序void showSort F(RecType R);int main(vo

4、id) int val;int i;RecType RMAXE;srand (unsigned)time(NULL);for(i=0;i=10;i+)Ri. key= (rand()%100+l);printf(產(chǎn)生的隨機(jī)數(shù)序列為：)； for(i=0;i=10;i+)printf(%3d，Ri. key);printf (n);printf (隨機(jī)輸入1到6數(shù)字：)； scanf(%d,&val);switch(val)case 1: InsertSort (R,10);printf(隨機(jī)數(shù)經(jīng)直接插入排序后：)； showSort(R);break;case 2:BlnsertSort(R,

5、 1, 10, 10);printf (隨機(jī)數(shù)經(jīng)折半插入排序后：)； showSort(R);break：case 3:ShellSort(R, 10);printf(隨機(jī)數(shù)經(jīng)希爾插入排序后：)； showSort_F(R);break;case 4:bubble_sort(R, 10);printf (隨機(jī)數(shù)經(jīng)起泡排序后：)； showSort_F(R);break;case 5:Quicksort(R, 0, 9);printf(隨機(jī)數(shù)經(jīng)快速排序后：)； showSortF(R);case 6:SelectSort(R, 10);printf (隨機(jī)數(shù)經(jīng)簡(jiǎn)單項(xiàng)選擇擇排序后：)； showS

6、ort_F(R);)return 0;void InsertSort(RecType R, int length) /對(duì)數(shù)組a作直接插入排序int i, j;for(i=2;i=length;+i)if (Ri. keyRi-l. key) / 需將 ai插入有序子表(R0. key=Ri. key; / 復(fù)制為哨兵Ri. key=RiT. key;for(j=i-2;R0. keyRj. key：j)Rj+1. key=Rj. key; / 記錄后移Rj+1. key=R0. key; / 插入到正確位置void BlnsertSort (RecType R, int low, int hi

7、gh, int length) (int m;for ( int i=2; i=length; +i )(R0.key = REiLkey; / 將 Ri暫存到 R0low = 1;high = i-1;while ( low = high) 在Rlow. high中折半查找插入的位置m = (low+high)/2;/ 折半if (R0.key =high+l; j )Rj+1. key = Rj. key; / 記錄后移REhigh+1. key = R0. key; / 插入 / BlnsertSort void ShellSort (RecType R, int n) /*希爾排序算法

8、*/ (int i, j, d, k;RecType temp;d=n/2;/*d 取初值 n/2*/while (d0) (for (i=d; i=0 & Rj. keyRj+d. key) (temp=Rj ;與 Rj+d交換*/Rj= Rj+d;Rj+d=temp;j二j-d;printf (，zd=%d: , d) ; /*輸出每一趟的排序結(jié)果*/for (k=0;kn;k+)printf(3d，Rk.key);printf (n);d=d/2;/*遞減增量d*/)void bubble_sort (RecType R, int length) /將a中整數(shù)序列重新排列成自小至大有序的

9、整數(shù)序歹U (起泡排序) int i, j, t;for(i=0;ilength-l;i+)(for(j=i+l；jRj. key)t=Ri. key;10Ri.key=Rj. key;Rj. key=t;)void Quicksort (RecType R, int low, int high)(int pos;if(lowhigh)pos=FindPos(R, low, high);Quicksort(R, low, pos-l);Quicksort(R, pos+1, high);)int FindPos (RecType R, int low, int high)(int val=Rl

10、ow. key;while(lowhigh)while(low=val)high;Rlow. key=Rhigh.key;while(1owhigh&R1ow. key=val) +low;Rhigh. key=Rlow, key;)Rlow, key=val;return high;)int SelectMinKey(RecType R, int i, int length) /返回在ai.length中key最小的記錄的序號(hào) int min;int j,k;k=i; /設(shè)第i個(gè)為最小 min=Ri. key;for(j=i+l;jlength;j+)if (Rj. keymin) / 找到

11、更小的(k二 j;min=Rj. key;return k;11void SelectSort (RecType R, int length) /對(duì)數(shù)組a作簡(jiǎn)單項(xiàng)選擇擇排序int i, j;int t;for(i=0;ilength-l;+i) /選擇第i小的記錄，并交換到位j=SelectMinKey (R, i, length) ; / 在 ai. . length中選擇最小的記錄 if(i!=j)與第i個(gè)記錄交換t=Ri.key;Ri. key=Rj. key;Rjkey=t;void showSort(RecType R)(int i;for(i=l;i=10;i+) printf (

12、，z%d，z, RiL key);)printf (n);void showSort_F(RecType R)(int i;for(i=0;i10;i+) printf (z，%d z，, Ri. key);)printf (n);124測(cè)試4.1測(cè)試數(shù)據(jù)由函數(shù)rand()產(chǎn)生的隨機(jī)數(shù)進(jìn)行測(cè)試。4. 2測(cè)試結(jié)果分析79 52 24 21 54 9 4 46 39 83 28陋圳輸入1期數(shù)字：1型機(jī)數(shù)經(jīng)直接插入排序后：4 9 21 24 28 39 46 52 54 83Press any key to continue圖-3直接插入排序當(dāng)輸入數(shù)字1時(shí)，主函數(shù)通過switch語句調(diào)用直接插入排序

13、，對(duì)數(shù)組進(jìn)行 從小到大的排序。產(chǎn)生的隨機(jī)數(shù)序列為:50 65 90 28 95 47 94 26 45 13 52 遁物頡人工到6數(shù)多4遁機(jī)數(shù)經(jīng)起泡排序后：13 26 28 45 47 50 65 90 94 95Press any key to continue圖1-4冒泡排序當(dāng)輸入數(shù)字4時(shí)，主函數(shù)通過switch語句調(diào)用冒泡排序，對(duì)數(shù)組進(jìn)行從小 到大的排序。135總結(jié)通過這次課程設(shè)計(jì)的學(xué)習(xí)讓我學(xué)會(huì)了許多，讓我對(duì)專業(yè)知識(shí)有了初步的了 解。在這次課程設(shè)計(jì)中，首先實(shí)現(xiàn)隨機(jī)數(shù)的生成，將生成的指定數(shù)目的隨機(jī)數(shù)一 一對(duì)應(yīng)的賦予定義的空數(shù)組,經(jīng)選擇語句分別執(zhí)行直接插入排序,折半插入排序, 希爾排序，起泡

14、排序，快速排序，簡(jiǎn)單項(xiàng)選擇擇排序等6種排序?qū)?shù)組中的數(shù)值進(jìn)行 排序。這次課程設(shè)計(jì)還有許多缺乏，如局部排序方法編程代碼過于復(fù)雜，此外， 由于編程各種排序方法的區(qū)別較大，使用了不同的輸出函數(shù)，增加了程序的復(fù)雜 性。此外，由于能力有限，還有無法實(shí)現(xiàn)的2種排序。但我也學(xué)到了很多東西， 如，掌握一些排序方法的實(shí)現(xiàn)，熟悉了編寫代碼的一般步驟：思考問題，寫出解 決方案，寫出偽代碼，完成代碼，調(diào)試程序。我從編寫過程中，發(fā)現(xiàn)自己更多的 缺乏，如對(duì)C語言的掌握不夠牢靠，對(duì)于C語言各種函數(shù)的調(diào)用也不夠靈活等。希望在以后的編程過程中，能更加耐心和細(xì)心，不熟悉也不要慌張，不慌不 忙的進(jìn)行程序編寫和調(diào)試。14參考文獻(xiàn)1數(shù)

15、據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏清華大學(xué)出版社20022數(shù)據(jù)結(jié)構(gòu)-C語言描述王路群中國(guó)水利水電出版社2007數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程（C語言版）王國(guó)鈞清華大學(xué)出版社20094數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏，吳偉民編 清華大學(xué)出版社2002C語言程序設(shè)計(jì)譚浩強(qiáng)清華大學(xué)出版社6C語言入門經(jīng)典霍頓（美）清華大學(xué)出版社15題目排序算法實(shí)現(xiàn)考核工程考核內(nèi)容得分平時(shí)考核（30分）出勤情況、態(tài)度、效率；知識(shí)掌握情況、 基本操作技能、知識(shí)應(yīng)用能力、獲取知識(shí)能力系統(tǒng)設(shè)計(jì)（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實(shí)現(xiàn)系統(tǒng)的各個(gè)功能模塊，并完成調(diào)試回答下列問題（15分）回答老師針對(duì)課程設(shè)計(jì)提出的問題課程設(shè)計(jì)報(bào)告撰寫（10分）嚴(yán)格按照規(guī)范要

16、求完成課程設(shè)計(jì)報(bào)告源代碼（5分）按照規(guī)范要求完成課程設(shè)計(jì)源代碼的排版總評(píng)成績(jī)指導(dǎo)教師評(píng)語：日期：年 月日 TOC o 1-5 h z 1課程設(shè)計(jì)目標(biāo)與任務(wù)1課程設(shè)計(jì)目標(biāo)1 HYPERLINK l bookmark18 o Current Document 課程設(shè)計(jì)任務(wù)1 HYPERLINK l bookmark20 o Current Document 課程設(shè)計(jì)基本要求12分析與設(shè)計(jì)22.1題目需求分析2 HYPERLINK l bookmark25 o Current Document 2. 2存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)3 HYPERLINK l bookmark27 o Current Document

17、 3算法描述3 HYPERLINK l bookmark0 o Current Document 程序流程圖7 HYPERLINK l bookmark2 o Current Document 程序測(cè)試說明7 HYPERLINK l bookmark4 o Current Document 3程序清單84.測(cè)試錯(cuò)誤!未定義書簽。.1測(cè)試數(shù)據(jù)13 HYPERLINK l bookmark9 o Current Document . 2測(cè)試結(jié)果分析13 HYPERLINK l bookmark11 o Current Document 5總結(jié)14 HYPERLINK l bookmark13 o

18、Current Document 參考文獻(xiàn)151課程設(shè)計(jì)目標(biāo)與任務(wù)1.1課程設(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é)的軟件工作 方法學(xué)生通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各方面得到鍛煉。1. 2課程設(shè)計(jì)任務(wù)設(shè)計(jì)排序相關(guān)函數(shù)庫(kù)，以便在程序設(shè)計(jì)中調(diào)用，要求設(shè)計(jì)程序，產(chǎn)生20000 個(gè)隨機(jī)數(shù)，完成下面功能：（1）對(duì)這些數(shù)分別進(jìn)行直接插入排序、折半插入排序、希爾排序、起泡排 序、快速排序、簡(jiǎn)單項(xiàng)選擇擇排序，堆排序，2路-歸并排序等排序，并把排序結(jié)果

19、進(jìn)行保存。（2）最好能借助語言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖 形方式顯示出來，將復(fù)雜的運(yùn)行過程以動(dòng)態(tài)方式顯示出來；（3）給出假設(shè)干例程，演示通過調(diào)用自己所寫程序來實(shí)現(xiàn)相關(guān)問題的要求。. 3課程設(shè)計(jì)基本要求嚴(yán)格按照題意要求，獨(dú)立進(jìn)行設(shè)計(jì)，不能隨意更改。假設(shè)確因條件所限，必須 要改變課題要求時(shí)，應(yīng)在征得指導(dǎo)教師同意的前提下進(jìn)行。學(xué)生應(yīng)制定實(shí)習(xí)工作 計(jì)劃，認(rèn)真完成實(shí)習(xí)的各個(gè)環(huán)節(jié)，并在老師的指導(dǎo)下認(rèn)真組織實(shí)習(xí)工作，撰寫實(shí) 習(xí)報(bào)告，做好實(shí)習(xí)總結(jié)。2分析與設(shè)計(jì). 1題目需求分析1,直接插入排序思路：設(shè)有一組關(guān)鍵字Kl,K2-.Kn）,排序開始便認(rèn)為K1是一個(gè)有序的 序列，讓K2插入到表長(zhǎng)為

20、1的有序序列，使之成為一個(gè)表長(zhǎng)為2的有序序列， 讓K3插入到表長(zhǎng)為2的有序序列，使之成為表長(zhǎng)為3的有序序列，依次類推， 最后Kn插入到上述表長(zhǎng)為n-1的有序序列，得到一個(gè)表長(zhǎng)為n的有序序列。.折半插入排序思路：在將一個(gè)新元素插入已排好序的數(shù)組的過程中，尋找插入點(diǎn)時(shí)，將待 插入?yún)^(qū)域的首元素設(shè)置為allow,末元素設(shè)置為ahigh,那么輪比擬時(shí)將待插入 元素與am,其中m=（low+high）/2相比擬,如果比參考元素小，那么選擇a low 到amT為新的插入?yún)^(qū)域（即high=m-l）,否那么選擇am+l到ahigh為新的插 入?yún)^(qū)域（即low=m+l）,如此直至lowChigh不成立，即將此位置之

21、后所有元素 后移一位，并將新元素插入ahigh+l。.希爾排序思路：先取一個(gè)小于n的整數(shù)dl作為第一個(gè)增量，把文件的全部記錄分組。 所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序； 然后，取第二個(gè)增量d2,d2dl,再將到d2作為增量繼續(xù)分組，再進(jìn)行直接插入 排序，依次向下取值，直到完成排序。.起泡排序思路：比擬相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。對(duì)每一 對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的 元素應(yīng)該會(huì)是最大的數(shù)。針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持續(xù) 每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比

22、擬。.快速排序思路：快速排序的實(shí)現(xiàn)基于分治法，具體分為三個(gè)步驟。假設(shè)待排序的序列 為序列Lm. n被劃分成兩個(gè)可能為空的子序列Lm . pivot-1 和Lpivot+1 . n,使Lm. pivotT的每個(gè)元素均小于或等于Lpivot, 同時(shí)Lpivot+1. n的每個(gè)元素均大于Lpivot。其中Lpivot稱為這一趟分 割中的主元(也稱為樞軸、支點(diǎn))。通過遞歸調(diào)用快速排序，對(duì)子序列Lm . pivotT和Lpivot+1 . r排序。由于兩個(gè)子序列是就地排序的，所以對(duì)它 們的合并不需要操作，整個(gè)序列Lm. n已排好序。.簡(jiǎn)單項(xiàng)選擇擇排序思路：序序列的記錄個(gè)數(shù)為n o i取1, 2,n-1,

23、從所有n-i+l個(gè)記錄(R, Ri+1,Rn中找出排序碼最小的記錄，與第i個(gè)記錄交換。執(zhí)行n-1趟 后 就完成了記錄序列的排序。2. 2存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)此程序采用的是線性表的動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)：ftdefine LIST_INIT_SIZE 100線性表存儲(chǔ)空間的初始分配量ftdefine LISTINCREMENT 10線性表存儲(chǔ)空間的分配增量Typedef struct ElemType *elem;存儲(chǔ)空間基址Int length;當(dāng)前長(zhǎng)度Int listsize;當(dāng)前分配的存儲(chǔ)容量(以sizeof (ElemType)為單位) SqList;上述定義中，數(shù)組指針elem指示存儲(chǔ)空間基址，le

24、ngth表示線性表的當(dāng)前長(zhǎng)度, 對(duì)線性表的初始化操作就是為順序表預(yù)定義大小的數(shù)組空間，并將線性表的當(dāng)前 長(zhǎng)度設(shè)為“0，listsize指示當(dāng)前分配的存儲(chǔ)空間大小，一旦元素插入而空間 缺乏，可進(jìn)行再分配。1. 3算法描述.直接插入排序設(shè)置R0為哨兵，將剩下的數(shù)值逐個(gè)進(jìn)行插入，直至完成一趟排序： void InsertSort ( elem R , int n) 對(duì)記錄序列RL.n作直接插入排序。for ( i=2; i=n; +i ) R0 = Ri;/復(fù)制為監(jiān)視哨3for ( j=i-l; R0 Rj; j )Rj+1= Rj;/ 記錄后移Rj+1=R0;/插入到正確位置) / InsertS

25、ort.折半插入排序因?yàn)槭且粋€(gè)按關(guān)鍵字有序的序列，那么可以利用折半查找實(shí)現(xiàn)“在中查找Ri的插入位置: void BlnsertSort (elem R , int n) /對(duì)記錄序列REI. 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; / 記錄后移Rhigh+1= R0 : / 插入 / BlnsertSort

26、.希爾排序先取一個(gè)正整數(shù)dKn,把所有相隔&的記錄放一組，組內(nèi)進(jìn)行直接插入排序，然后取d2d”重復(fù)上述分組和排序操作；直至即所有記錄放進(jìn)一個(gè) 組中排序?yàn)橹梗簐oid Shelllnsert ( elem R , int dk ) /對(duì)待排序列R作一趟希爾插入排序 for ( i=dk+l; i=n; +i )if ( Ri Ri-dk) void ShellSort (elem R , int d , int t) 按增量序列d 0. t-l對(duì)順序表L作希爾排序。 for ( k=0; k0 & R01)(for ( j = 1; j i; j+ )if (R j+1 R j )(Swap(R j , R