各種排序的算法報告及源程序

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

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

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

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

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

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

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

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

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

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

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

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 將隨機數(shù)寫入程序·································&#

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

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

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

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

21、;··········175.2 個人體會······································&

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

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

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

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

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

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

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

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

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

32、間的數(shù)，所以采用了分別獲取0到10000之間的數(shù)加上0到10之間的數(shù)最終得到0到100000之間的數(shù)的方法。但是rand()函數(shù)具有重復(fù)性，并且這種重復(fù)性可用于驗證該函數(shù)運行正確與否，故要借助srand()、time()對該函數(shù)進(jìn)行隨機化。其中，函數(shù)time的返回值是以秒為單位的從1970年1月1日午夜開始到現(xiàn)在所經(jīng)歷的時間，time函數(shù)的返回值被轉(zhuǎn)換成一個無符號的種子傳遞給srand()函數(shù)以產(chǎn)生隨機數(shù)表 隨機數(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 圖 隨機數(shù)生成流程圖 時間函數(shù)的產(chǎn)生時間函數(shù)的用法，參考如下程序，使用時間函數(shù)，需要引入頭文件time.h，同時需要使用函數(shù)clock()，clock()函數(shù)返回近似調(diào)用程序運行時間量的值,該值除以CLOCKS_PER_SEC后轉(zhuǎn)換為秒數(shù).返回-1值表示無法取得時間。#include<stdio.h>#include<time.h>void main

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

35、d語句計算出選擇排序所用的時間，用for循環(huán)語句得出比較次數(shù)和交換次數(shù)。用printf將選擇排序時間，比較次數(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)語句，對“BeforeSort.txt“中的隨機數(shù)進(jìn)行選擇排序，并打開“In

37、sertSort.txt”文本文檔，將經(jīng)過插入排序的數(shù)放入該文本文檔。用clock-start及clock-end語句計算出插入排序所用的時間，用for循環(huán)語句得出比較次數(shù)和交換次數(shù)。用printf將插入排序時間，比較次數(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)語句，對“BeforeSort.txt

39、“中的隨機數(shù)進(jìn)行選擇排序，并打開“PoptSort.txt”文本文檔，將經(jīng)過冒泡排序的數(shù)放入該文本文檔。用clock-start及clock-end語句計算出冒泡排序所用的時間，用for循環(huán)語句得出比較次數(shù)和交換次數(shù)。用printf將冒泡排序時間，比較次數(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將隨機數(shù)組寫入文件 隨機數(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)入主界面的框架?！皻g迎”界面程序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個隨機數(shù)經(jīng)過選擇排序、插入排序、冒泡排序后的結(jié)果界面。通過這個界面，可以清楚得得到三種排序方法各自的排序時間、比較次數(shù)以及交換次數(shù)。圖2三種排序各自的結(jié)

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

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

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

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