各種排序的算法報(bào)告及源程序

1、摘要近幾年來，C語言發(fā)展迅速，而且成為最受歡迎的語言之一，主要原因是它具有強(qiáng)大的功效，很多著名的系統(tǒng)軟件就是由C語言編寫出來的。它與匯編語言的結(jié)合，更體現(xiàn)出C語言的優(yōu)越性。排序算法主要有直接插入排序，折半插入排序，希爾排序，冒泡排序，雙向冒泡排序，快速排序，選擇排序，堆排序，基數(shù)排序這幾種。通過對(duì)各種排序方法的比較，我們能夠很直觀的發(fā)現(xiàn)各種排序方法的特點(diǎn)及各自的優(yōu)缺點(diǎn)。此次課程設(shè)計(jì)主要挑選了選擇排序、插入排序、冒泡排序這三種排序方法，通過對(duì)這三種排序方法的比較，希望能夠讓大家對(duì)一些排序方法有更加直觀、深入的了解。設(shè)計(jì)中主要解決了用time()、srand()函數(shù)輔助rand()函數(shù)隨機(jī)產(chǎn)生了0

2、到99999之間的數(shù)據(jù)；借助指針申請(qǐng)了動(dòng)態(tài)內(nèi)存解決了將同一隨機(jī)數(shù)組的三次復(fù)制進(jìn)而確保在相同隨機(jī)數(shù)組的基礎(chǔ)上三種比較算法的比較；在各種算法中運(yùn)用clock()函數(shù)計(jì)算完成比較所用的時(shí)間，并在各種比較算法的編程理解中完成比較、交換次數(shù)的計(jì)數(shù)；將隨機(jī)數(shù)組寫入文件等問題。關(guān)鍵詞：隨機(jī)數(shù) 排序 交換 時(shí)間 目錄1. 設(shè)計(jì)內(nèi)容、設(shè)計(jì)參數(shù)及要求······················&#

3、183;················11.1 設(shè)計(jì)內(nèi)容································

4、;···················11.2 設(shè)計(jì)參數(shù)·····························&#

5、183;·····················11.3 要求···························&

6、#183;···························12. 總體設(shè)計(jì)思路····················

7、83;······························22.1 設(shè)計(jì)系統(tǒng)的功能·················

8、83;···························22.2 算法思想·····················

9、······························22.3 系統(tǒng)的總體框架··················

10、···························32.4 系統(tǒng)的總體流程圖·····················

11、;······················43. 功能模塊的具體設(shè)計(jì)·························

12、3;···················53.1 main( )主函數(shù)····························&

13、#183;··················53.2 SelectSort( )函數(shù)····························

14、;·················73.3 InsertSort( )函數(shù)·····························

15、83;···············93.4 PopSort( )函數(shù)·······························

16、3;··············113.5 將隨機(jī)數(shù)寫入程序·································&#

17、183;········133.6 welcome( )函數(shù)······································&#

18、183;······144. 模塊的調(diào)試及測試·········································&

19、#183;····155. 總結(jié)與個(gè)人體會(huì)···········································&

20、#183;····175.1 總結(jié)············································

21、;··········175.2 個(gè)人體會(huì)······································&

22、#183;···········176. 致謝·····································

23、·····················197. 參考文獻(xiàn)···························

24、83;··························20附程序源代碼······················&

25、#183;······························211. 設(shè) 計(jì) 內(nèi) 容 和 要 求1.1 設(shè)計(jì)內(nèi)容通過隨機(jī)函數(shù)隨機(jī)生成100000個(gè)數(shù)字，這些數(shù)字都是在0，99999之間。(2)并通過設(shè)計(jì)的排序算法進(jìn)行排序。這些排序算法中包括冒泡法、選擇法、插入法，也可以適當(dāng)選擇其他算法，但

26、必須是較為典型的排序算法。(3)排序完畢后應(yīng)給出相應(yīng)的比較信息，其中包括排序時(shí)間，比較次數(shù)和交換次數(shù)等信息。(4)在程序的主界面顯示出最后的比較結(jié)論。(5)查看完比較結(jié)果后，即可點(diǎn)擊回車退出系統(tǒng)1.2 設(shè)計(jì)參數(shù)(1)將排序前生成的100000個(gè)隨機(jī)數(shù)存入一個(gè)文本文件中，該文件命名為BeforeSort.txt。(2)將排序好的數(shù)字分別按照不同的排序方式存入不同的文件中，冒泡法排序后的數(shù)字存入PopSort.txt中，選擇法排序后的數(shù)字存入SelectSort.txt中，插入法排序后的數(shù)字存入InsertSort.txt中。1.3 要求 基本要求精確測試上述三種排序方法對(duì)同樣的數(shù)據(jù)進(jìn)行排序所消耗

27、的時(shí)間，比較次數(shù)以及交換次數(shù)，明確各種排序的編寫方法，分析各種排序方法在不同情況下的優(yōu)劣。 附加要求（1）程序啟動(dòng)后有較漂亮的封面頁。(2 ) 結(jié)果以列表形式，較友好的人機(jī)界面顯示2. 總 體 設(shè) 計(jì) 思 路2.1 設(shè)計(jì)系統(tǒng)的功能在“Before.txt”中存儲(chǔ)隨機(jī)數(shù)。在”SelectSort.txt”、”InsertSort.txt”、”PopSort.txt”中存儲(chǔ)經(jīng)過排序后的有序數(shù)列。通過對(duì)主界面中三種排序方法所用時(shí)間、比較次數(shù)、交換次數(shù)等信息的觀察，了解到各自排序方法的特點(diǎn)及優(yōu)劣。2.2 算法思路 選擇排序?yàn)榱吮阌诶斫?，設(shè)有10個(gè)數(shù)分別存在數(shù)組元素a0a9中。選擇排序法是由大到小依次定

28、位a0a9中恰當(dāng)?shù)闹?，a9中放的自然是最小的數(shù)。如定位a0,先假定a0中當(dāng)前值是最大數(shù)，a0與后面的元素一一比較，如果a4更大，則將a0、a4交換，a0已更新再與后面的a5a9比較，如果a8還要大，則將a0、a8交換，a0又是新數(shù)，再與a9比較。一輪比完以后，a0就是最大的數(shù)了，本次比武的武狀元誕生了，接下來從a1開始，再來一輪a1就是次大的數(shù)，然后從a2開始，當(dāng)比到a8以后，排序就完成了。 插入排序每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序，直到待排序數(shù)據(jù)元素全部插入完為止。即經(jīng)過i-1遍處后,L1.i-1己排好序。第i遍處理僅將L插入L1.i-1的適

29、當(dāng)位置p，原來p后的元素一一向右移動(dòng)一個(gè)位置,使得L1.i又是排好序的序列。冒泡排序首先將第一個(gè)記錄的隨機(jī)數(shù)和第二個(gè)記錄的隨機(jī)數(shù)進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的隨機(jī)數(shù)。依此類推，直到第N-1和第N個(gè)記錄的隨機(jī)數(shù)進(jìn)行過比較為止。上述為第一趟排序，其結(jié)果使得關(guān)鍵字的最大紀(jì)錄被安排到最后一個(gè)記錄的位置上。然后進(jìn)行第二趟起泡排序，對(duì)前N-1個(gè)記錄進(jìn)行同樣操作。一共要進(jìn)行N-1趟起泡排序2.3系統(tǒng)的總體框架圖登錄選擇排序插入排序冒泡排序?qū)⑴判蚪Y(jié)果放入文件將排序結(jié)果放入文件將排序結(jié)果放入文件結(jié)束主函數(shù)退出2.4 系統(tǒng)的總體流程圖調(diào)用隨機(jī)數(shù)函數(shù)，產(chǎn)生10000個(gè)隨機(jī)數(shù)打

30、開一個(gè)“BeforeSort.txt”文本文檔，將這10000個(gè)隨機(jī)數(shù)放到文本文檔中選擇排序，并得出其時(shí)間消耗，比較次數(shù)，交換次數(shù)插入排序，并得出其時(shí)間消耗，比較次數(shù)，交換次數(shù)冒泡排序，并得出其時(shí)間消耗，比較次數(shù)，交換次數(shù)將經(jīng)過選擇排序好的10000個(gè)數(shù)字存放到“SelectSort.txt”文本文檔將經(jīng)過插入排序好的10000個(gè)數(shù)字存放到“InsertSort.txt”文本文檔將經(jīng)過排序好的10000個(gè)數(shù)字存放到“PopSort.txt”文本文檔程序結(jié)束退出進(jìn)入登錄界面按“Enter”鍵進(jìn)入主界面3.功能模塊的具體設(shè)計(jì)3.1 main( ) 主函數(shù)主函數(shù)功能比較簡單，用srand( (uns

31、igned)time( NULL ) )語句以及for循環(huán)語句產(chǎn)生隨機(jī)數(shù)。打開"BeforeSort.txt"文本文檔，將隨機(jī)數(shù)放入該文本文檔中。使用動(dòng)態(tài)內(nèi)存，定義選擇、插入、冒泡三種排序方法。在主函數(shù)的前面要寫必須的頭文件，預(yù)定義語句。隨機(jī)函數(shù)的產(chǎn)生函數(shù)rand()將產(chǎn)生一個(gè)在0到RAND_MAX之間的整數(shù)，其中RAND_MAX是頭文件< stdio.h >中定義的一個(gè)符號(hào)常量，并且至少是32767，即16位二進(jìn)制數(shù)所能表示的最大整數(shù)。并可以利用比例縮放（求余運(yùn)算）產(chǎn)生一系列0到所需數(shù)（小于RAND_MAX）之間的數(shù) 。但實(shí)際操作中最大只能得到0到10000之

32、間的數(shù)，所以采用了分別獲取0到10000之間的數(shù)加上0到10之間的數(shù)最終得到0到100000之間的數(shù)的方法。但是rand()函數(shù)具有重復(fù)性，并且這種重復(fù)性可用于驗(yàn)證該函數(shù)運(yùn)行正確與否，故要借助srand()、time()對(duì)該函數(shù)進(jìn)行隨機(jī)化。其中，函數(shù)time的返回值是以秒為單位的從1970年1月1日午夜開始到現(xiàn)在所經(jīng)歷的時(shí)間，time函數(shù)的返回值被轉(zhuǎn)換成一個(gè)無符號(hào)的種子傳遞給srand()函數(shù)以產(chǎn)生隨機(jī)數(shù)表 隨機(jī)數(shù)的產(chǎn)生 中間變量Ri = ka= rand()%10000b = a*10c = rand()%10k = b+cR 05465R1723R28421R369R43623i = 0i

33、 < Na = rand()%10000rand()%10000b = a*10 c = rand()%10rand()%10k = b+cRi = ki +真int i,a,b,c,k,RNrand()%10000 圖 隨機(jī)數(shù)生成流程圖 時(shí)間函數(shù)的產(chǎn)生時(shí)間函數(shù)的用法，參考如下程序，使用時(shí)間函數(shù)，需要引入頭文件time.h，同時(shí)需要使用函數(shù)clock()，clock()函數(shù)返回近似調(diào)用程序運(yùn)行時(shí)間量的值,該值除以CLOCKS_PER_SEC后轉(zhuǎn)換為秒數(shù).返回-1值表示無法取得時(shí)間。#include<stdio.h>#include<time.h>void main

34、()clock_t start;clock_t end;int t;long i;start=clock(); /得到程序運(yùn)行時(shí)的時(shí)間量的值for(i=0;i<=10000;i+); /空循環(huán)，耗費(fèi)時(shí)間end=clock();t=(end-start)/CLOCKS_PER_SEC; /得到空循環(huán)運(yùn)行的時(shí)間printf("%d",t);3.2SelectSort（）函數(shù)利用for循環(huán)語句，對(duì)“BeforeSort.txt“中的隨機(jī)數(shù)進(jìn)行選擇排序，并打開“SelectSort.txt”文本文檔，將經(jīng)過選擇排序的數(shù)放入該文本文檔。用clock-start及clock-en

35、d語句計(jì)算出選擇排序所用的時(shí)間，用for循環(huán)語句得出比較次數(shù)和交換次數(shù)。用printf將選擇排序時(shí)間，比較次數(shù)以及交換次數(shù)這些信息在主界面中輸出。，選擇排序程序void SelectSort(int R ,int n) /*選擇排序 int i,k,index,temp; double count1=0.0,cpt1=0.0; FILE*fp; clock_t start; clock_t end; double time1; start=clock(); for(k=0;k<n-1;k+) index=k; for(i=k+1;i<n;i+) cpt1+; if(Ri<Ri

36、ndex) index=i; if(index!=k) count1+; temp=Rindex; Rindex=Rk; Rk=temp;k = 0k < n-1int i , k, index , tempdouble count1,cpt1temp=RindexRindex=RkRk=temp真index =kRi < Rindexcpt1+ Index! =k i+ index = i真count1+ 真k+i < ni =k+1圖選擇排序流程圖3.3 InsertSort（）函數(shù)利用for循環(huán)語句，對(duì)“BeforeSort.txt“中的隨機(jī)數(shù)進(jìn)行選擇排序，并打開“In

37、sertSort.txt”文本文檔，將經(jīng)過插入排序的數(shù)放入該文本文檔。用clock-start及clock-end語句計(jì)算出插入排序所用的時(shí)間，用for循環(huán)語句得出比較次數(shù)和交換次數(shù)。用printf將插入排序時(shí)間，比較次數(shù)以及交換次數(shù)這些信息在主界面中輸出。插入排序程序void InsertSort(int R,int n) /*插入排序*/ int i,j,temp; double count2=0,cpt2=0,cpt3=0; FILE*fp; clock_t start; clock_t end; double time2; start=clock(); for(i=1;i<n;i

38、+) temp=Ri; for(j=i-1;j>=0;j-) cpt2+; if(temp>=Rj) break; Rj+1=Rj; Rj+1=temp; if(j+1=i-1) count2+; else count2=count2+0;i = 1i < nint i,j,tempdouble count2,cpt2,cpt3count2+真temp=Ricpt2+ Rj+1=temp j-Rj+1=Rj否j+1=i-1 i+ j = i-1j >= 0break是真假圖 插入排序流程圖3.4 Popsort（）函數(shù)利用for循環(huán)語句，對(duì)“BeforeSort.txt

39、“中的隨機(jī)數(shù)進(jìn)行選擇排序，并打開“PoptSort.txt”文本文檔，將經(jīng)過冒泡排序的數(shù)放入該文本文檔。用clock-start及clock-end語句計(jì)算出冒泡排序所用的時(shí)間，用for循環(huán)語句得出比較次數(shù)和交換次數(shù)。用printf將冒泡排序時(shí)間，比較次數(shù)以及交換次數(shù)這些信息在主界面中輸出。3.4.1 冒泡排序程序void PopSort(int R ,int n) /*冒泡排序*/ int i,j,t; double count3=0.0, cpt4=0.0; FILE*fp; clock_t start; clock_t end; double time3; start=clock();

40、for(i=1;i<n;i+) for(j=0;j<n-i;j+) if(Rj>Rj+1) count3+; t=Rj; Rj=Rj+1; Rj+1=t; cpt4+; i = 1i < nj = 0j < n-iRj > Rj+1t =Rjint i, j, t,double count3,cpt4Rj=Rj+1 Rj+1= t cpt4+ j +count3+ i+ 真真真假圖 冒泡排序流程圖3.5將隨機(jī)數(shù)組寫入文件 隨機(jī)數(shù)組寫入程序int *p=NULL; FILE*fp;if(fp=fopen("BeforeSort.txt",&

41、quot;w") = NULL) printf("error"); exit(0);for(i=0;i<n;i+)fprintf(fp,"%d ",Ri); if(fclose(fp)printf("Can not close the file"); exit(0);int i, *fp,nrand()%10000fp=fopen("BeforeSort.txt","w")fprintf(fp,"%d ",Ri)i +真fclose(fp)假 i < n

42、i = 0圖文件寫入流程圖3.6 welcome（）函數(shù)利用system("cls")系統(tǒng)語句，構(gòu)建敲擊”Enter”鍵進(jìn)入主界面的框架。“歡迎”界面程序void welcome()printf("n"); printf("n"); printf(" n"); printf(" 各種排序算法比較 n"); printf(" - n"); printf(" (c)All Right Reserved wyy n"); printf(" wcnumb

43、erond n"); printf(" version 2009 n"); printf(" n"); printf(" Press Enter to Continue");getchar(); system("cls"); 4. 模 塊 的 調(diào) 試 及 測 試圖1為測試歡迎“登陸”界面，當(dāng)按“Enter”鍵進(jìn)入下一界面。圖1 登陸界面圖2為測試10000個(gè)隨機(jī)數(shù)經(jīng)過選擇排序、插入排序、冒泡排序后的結(jié)果界面。通過這個(gè)界面，可以清楚得得到三種排序方法各自的排序時(shí)間、比較次數(shù)以及交換次數(shù)。圖2三種排序各自的結(jié)

44、果5. 總 結(jié) 與 個(gè) 人 體 會(huì)5.1 總結(jié) 該“排序算法比較”基本可以運(yùn)行，但是還是有不少地方設(shè)計(jì)的不太科學(xué)，而且有些在C語言課程設(shè)計(jì)指導(dǎo)書上的任務(wù)要求沒有很好得運(yùn)行出來。同時(shí)在這次課程設(shè)計(jì)中讓我們認(rèn)識(shí)到做程序設(shè)計(jì)這項(xiàng)工作中我門要具備以下素質(zhì)：良好的文檔是正規(guī)研發(fā)流程中非常重要的環(huán)節(jié)，缺乏文檔，一個(gè)軟件系統(tǒng)就缺乏生命力，在未來的查錯(cuò)，升級(jí)以及模塊的復(fù)用時(shí)就都會(huì)遇到極大的麻煩。 此外編程是一項(xiàng)高精度的工作所以我們要有規(guī)范化，標(biāo)準(zhǔn)化的代碼編寫習(xí)慣通過這次編程我們深深的感受到對(duì)代碼的變量命名，代碼內(nèi)注釋格式，甚至嵌套中行縮進(jìn)的長度和函數(shù)間的空行數(shù)字都有明確規(guī)定，良好的編寫習(xí)慣，不但有助于代碼的移

45、植和糾錯(cuò)，也有助于不同人員之間的協(xié)作。我們還要有模塊化思維能力，模塊化思維就是編程任何一個(gè)功能模塊或函數(shù)的時(shí)候，要多想一些，不要局限在完成當(dāng)前任務(wù)的簡單思路上，想想看該模塊是否可以脫離這個(gè)系統(tǒng)存在，是否可以通過簡單的修改參數(shù)的方式在其他系統(tǒng)和應(yīng)用環(huán)境下直接引用，這樣就能極大避免重復(fù)性的開發(fā)工作。5.2 個(gè)人體會(huì) 通過本次的C語言課程設(shè)計(jì)，對(duì)C語言 有了更深入的了解，本來對(duì)C語言一些函數(shù)、循環(huán)和結(jié)構(gòu)變量不是很清楚，運(yùn)用起來常常出錯(cuò)。但是如今通過2周的C語言程序設(shè)計(jì)，已經(jīng)可以熟練正確地運(yùn)用各類函數(shù)、循環(huán)變量、結(jié)構(gòu)化的程序設(shè)計(jì)以及指針。了解到模塊在C語言中運(yùn)用方式及技巧，為編寫一些比較復(fù)雜的語句及結(jié)

46、構(gòu)奠定了基礎(chǔ)。在編寫程序過程中，發(fā)現(xiàn)這確實(shí)是有一定難度的，必須對(duì)整個(gè)設(shè)計(jì)要求有很好得了解，才能在編寫中避免錯(cuò)誤的產(chǎn)生。而且在編寫時(shí)一定要仔細(xì)認(rèn)真地對(duì)待每個(gè)程序塊，尤其要搞清楚指針的指向。 由于知識(shí)的局限性，對(duì)一些錯(cuò)誤不能正確的將它改正。通過老師及同學(xué)才將錯(cuò)誤改正完畢。 經(jīng)過這次課程設(shè)計(jì)，我發(fā)現(xiàn)自己存在很多不足之處，我將會(huì)在以后的學(xué)習(xí)中把它們改正過來，努力將C語言學(xué)得更好。6. 致 謝首先感謝學(xué)校為我們提供了這么好的一個(gè)學(xué)習(xí)、提升能力的機(jī)會(huì)以及如此好的上機(jī)環(huán)境。然后感謝這兩周內(nèi)陪我們一路走來的各位指導(dǎo)老師，在這么炎熱的天氣里為我們做指導(dǎo)。尤其是向毅老師，感謝您對(duì)我們的嚴(yán)格要求，并為我們整理了這么

47、完整的C語言課程設(shè)計(jì)指導(dǎo)書以及課程設(shè)計(jì)報(bào)告要求。同時(shí)也感謝同學(xué)在編寫課程中對(duì)我的幫助，為我指出不足，讓我的程序更加羽翼豐滿。7參考文獻(xiàn) 王旭等編著.C語言實(shí)用界面技術(shù).陜西：西北工業(yè)大學(xué)出版社，1996 何欽銘 顏暉主編.C語言程序設(shè)計(jì). 高等教育出版社，2008 顏暉主編.C語言程序設(shè)計(jì)實(shí)驗(yàn)指導(dǎo).高等教育出版社，2008程序源代碼#include <stdlib.h> #include <stdio.h> #include <conio.h>#include <time.h>void welcome();void time();void Sel

48、ectSort(int R ,int n);void InsertSort(int R ,int n); void PopSort(int R ,int n); void main( ) /主函數(shù) system("color 2f");welcome(); int i,k,a,b,c,R100000,n;int *p=NULL; FILE*fp; srand( (unsigned)time( NULL ) ); for( i = 0; i <100000;i+ ) a=rand()%10000; b=a*10; c=rand()%10; k=b+c; Ri=k;n=1

49、00000;if(fp=fopen("BeforeSort.txt","w") = NULL) printf("error"); exit(0);for(i=0;i<n;i+)fprintf(fp,"%d ",Ri); if(fclose(fp)printf("Can not close the file"); exit(0);printf("Reslut:nnn");p=(int*)malloc(sizeof(int)*100000); for(i=0;i<n;

50、i+)pi=Ri; SelectSort(p,n);/選擇排序 for(i=0;i<n;i+)pi=Ri;InsertSort(p,n);/插入排序for(i=0;i<n;i+)pi=Ri; PopSort(p,n);/冒泡排序getch();void SelectSort(int R ,int n) /*選擇排序*/ int i,k,index,temp; double count1=0.0,cpt1=0.0; FILE*fp; clock_t start; clock_t end; double time1; start=clock(); for(k=0;k<n-1;k+

51、) index=k; for(i=k+1;i<n;i+) cpt1+; if(Ri<Rindex) index=i; if(index!=k) count1+; temp=Rindex; Rindex=Rk; Rk=temp; if(fp=fopen("SelectSort.txt","w") = NULL)printf("error");exit(0);for(i=0;i<n;i+)fprintf(fp,"%d ",Ri); if(fclose(fp)printf("Can not c

52、lose the file");exit(0); end=clock(); time1=(double)(end-start)/CLOCKS_PER_SEC; printf("=n"); printf("SelectSort:n"); printf("Select Sort Spend %.2lf secondsn",time1); printf("Select Sort Compare %.0lf timesn",cpt1); printf("Select Sort Swap %.0lf timesn",count1); printf("nn"); void InsertSort(int R,int n) /*插入排序*/ int i,j,temp; double count2=0,cpt2=0,cpt3=0; FILE*fp; clock_t start; clock_t end; double time2; start=clock(); for(i=1;i<n;i+) te