武漢理工數(shù)據(jù)結(jié)構(gòu)排序算法比較實驗報告

1、學(xué)生學(xué)號實驗課成績武漢理工大學(xué)學(xué)生實驗報告書實驗課程名稱數(shù)據(jù)結(jié)構(gòu)與算法開課學(xué)院計算機科學(xué)與技術(shù)學(xué)院指導(dǎo)教師姓名學(xué)生專業(yè)班級計算機類20172018學(xué)年第一學(xué)期實驗課程名稱:高級語言程序設(shè)計實驗項目名稱內(nèi)部排序算法比較實驗成績實驗者專業(yè)班級組別同組者實驗日期年 月日第一部分：實驗分析與設(shè)計(可加頁)一、實驗內(nèi)容描述(問題域描述)內(nèi)部排序算法比較。編制一個演示內(nèi)部排序算法比較的程序。對起泡排序、直接插入排序、簡單選擇排序、快速排序、希爾排序、歸并排序算法進行比較。二、實驗基本原理與設(shè)計(包括實驗方案設(shè)計，實驗手段的確定，試驗步驟等，用硬件邏輯或 者算法描述)(1)偽隨機產(chǎn)生數(shù)據(jù)：用偽隨機產(chǎn)生程序產(chǎn)

2、一組隨機數(shù)，再用不同排序算法進行排序。(2)簡單選擇排序：運用簡單選擇排序法對偽隨機產(chǎn)生的數(shù)據(jù)進行排序。(3)起泡排序：運用起泡排序法對偽隨機產(chǎn)生的數(shù)據(jù)進行排序。(4)直接插入排序：運用直接插入排序法對偽隨機產(chǎn)生的數(shù)據(jù)進行排序。(5)希爾排序：運用希爾排序法對偽隨機產(chǎn)生的數(shù)據(jù)進行排序。(6)快速排序：運用快速排序法對偽隨機產(chǎn)生的數(shù)據(jù)進行排序。(7)歸并排序：運用歸并排序法對偽隨機產(chǎn)生的數(shù)據(jù)進行排序。定義抽象數(shù)據(jù)類型typedef structint key;ElemType; / 關(guān)鍵字typedef structElemType *elem;int length;SqList;/本實驗使用線

3、性表的存儲結(jié)構(gòu)三、主要儀器設(shè)備及耗材PCDev-C+ 5.11Sublime Text 3 編摘弟二部分：實驗調(diào)試與結(jié)果分析（可加頁）一、調(diào)試過程（包括調(diào)試方法描述、實驗數(shù)據(jù)記錄，實驗現(xiàn)象記錄，實驗過程發(fā)現(xiàn)的問題等） C:UserlhaseeDektop：apS 1 .exe清輸入你要輸入的今徵：10 口加力序用時為:為為要 續(xù)數(shù)時保 SMA:為為要 序爵你 裳用人 示:為: 款用人 才出排清:為為要 你 費用人 SS 直比排清曲985 gL移動次數(shù)為 j. LlbuiU日葡人你要輸入的怪的叩999眈。乳移動次數(shù)為 0. 401000輸入的個數(shù)二10口皿花43Ml移動次敝為 0. 081000

4、 輸入的今教：二口我。15126go。移動次數(shù)為0, 031000個數(shù)二00002995275199347249011912&8B015163216Si755茹移動次數(shù)為 0. 000000136320宓*非*_*1比較次數(shù)*#冢*京才* 中我*歸并排序*壯*年選擇排序5旦1：樹/我*+*:*季相*中京辛冒泡排序E*構(gòu)件*率和件!M：步神華樣粕忤科華杵柏性！*日*季*尋*直插排序:搟本搟啪搟!K+事?lián){/搟*M* W非*_*1玳希爾排扁:=*科*斗*+*+豐*+*+快排排序 E4o|c*d|:*靠*本求說才:*才2二, I/ 希爾排序:選擇排序,* * 豐*+冒泡排序;*木*#*本*本*#*本*

5、我*本*津木*豐*京率*元*非*靠*布*京*直插排序:+4#+*木毛+4*+4*#*+4*林*4 *布快排排序,歸并排序:*金排序月時水 * * * *1和 土 * * 市*篇爾排序：*怛E*斗興代牛比軍比*本非獨和口中選擇H 卡序 S31tlM單*:X*卜/小片*黨*itkit*樹木桂展 泡田 片 EsHek*5ki*it：KH *;*4*K3tk* * *在日*宣茴由L子；在門我* *中十寸* * 中依+寸中快郁排南：H*樹四*d*.*dk. I sV / ah * ah 本 |. *_ 十 .歸并排生:*小#1f事*本月雜惠本*茶柜本村才Ftccecs QEttsd ait&r 1.1.

6、52 seconds vith return 71ue 0 育接任意錠強急，二、實驗結(jié)果及分析(包括結(jié)果描述、實驗現(xiàn)象分析、影響因素討論、綜合分析和結(jié)論等)實驗結(jié)果只有在待排序個數(shù)數(shù)目比較大的時候才能體現(xiàn)更明顯的區(qū)別。實驗運行成功，整體符合預(yù)期。簡單選擇排序：運用順序表。時間復(fù)雜度O(n2),空間復(fù)雜度 0(1)。起泡排序：時間復(fù)雜度 0(n2),空間復(fù)雜度 0(1)直接插入排序：時間復(fù)雜度0(n2),空間復(fù)雜度 0(1)希爾排序：時間復(fù)雜度 0(n1.3),空間復(fù)雜度0(1)快速排序：時間復(fù)雜度 O(nlog 2n),空間復(fù)雜度 O(nlog 2n)歸并排序：時間復(fù)雜度 O(nlog 2n)

7、,空間復(fù)雜度0(n)三、實驗小結(jié)、建議及體會深入學(xué)習(xí)理解各種排序方法的性能差別：排序算法的性能評估穩(wěn)定性(假設(shè)記錄 a和記錄b都位于待排序的序列中)(1)穩(wěn)定：如果a本來就在b前面，且a = b ,排序之后a仍然在b前面；(2)不穩(wěn)定：如果a本來就在b前面，且a = b ,排序之后a可能出現(xiàn)在b后面；待排序的記錄是否全部被放置在內(nèi)存中(1)內(nèi)排序：在整個排序過程中，待排序的所有記錄全部被放置在內(nèi)存中；(文中的所有排序算法都屬于內(nèi)排序)(2)外排序：由于排序的記錄個數(shù)太多，不能同時放置在內(nèi)存，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進行；時間復(fù)雜度：排序算法的時間開銷空間復(fù)雜度：排序算法所需

8、的存儲空間算法本身的復(fù)雜度。從平均情況來看，堆排序，歸并排序和快速排序算法要勝過希爾排序，并遠遠超過冒泡，選擇和插入排序的三種簡單算法；從最好情況來看，冒泡和插入排序算法要比其他算法更勝一籌，也就是說如果待排序的序列基本有序，則可以選擇這兩種排序算法；從最壞情況來看，堆排序和歸并排序要由于快速排序以及其他簡單排序；從空間復(fù)雜度來看，除了歸并排序和快速排序之外，其余算法對輔助空間的要求一致，都是0(1);如果排序過程中，對空間復(fù)雜度有要求，則不建議選擇歸并排序和快速排序。從穩(wěn)定性來看，改進算法中，只有歸并排序是穩(wěn)定的，而簡單排序都是穩(wěn)定的；從待排序的記錄的個數(shù)看，如果待排序的個數(shù)n越小，則采用簡

9、單排序算法比較合適；如果待排序的個數(shù)n越大，則采用改進排序算法更合適。四、附件：實驗代碼1) #include2) #include3) #include4) #include5) #include6) #define LIST_INIT_SIZE 300007) int bj1,yd1,n,com,mov;8) long int A5,B5;9) double t0,t1,t2,t3,t4,t5,C5;10) clock_t start_t,end_t;11) typedef struct12) 13) int key;14) ElemType;15) typedef struct16) 1

10、7) ElemType *elem;18) int length;19) SqList;20) void addlist(SqList &L)21) 22) int i;23) a: printf(請輸入你要輸入的個數(shù)：)；24) scanf(%d,&n);25) if(n20000)26) 27) printf(超出范圍重新輸入！!n);28) goto a;29) 30) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);31) if(!L.elem)exit(0);32) L.length=0;33) for(i=1;i20

11、000)goto b;37)+L.length;38)39)40)void SelectSort(SqList &L)/簡單選擇排序41)42)start_t=clock();43)int i,j,k,com=0,mov=0;44)for(i=1;iL.length;i+)45)46)k=i;47)for(j=i+1;jL.length;j+)48)49)com+;50)if(L.elemj.keyL.elemk.key)k=j;51)52)if(i!=k)53)54)L.elem0.key=L.elemi.key;55)L.elemi.key=L.elemk.key;56)L.elemk.k

12、ey=L.elem0.key;57)mov+=3;58)59)60)end_t=clock();61)printf(比較次數(shù)為%d 移動次數(shù)為dn,com,mov);62)t0=(double)(end_t-start_t)/CLK_TCK;63)printf(排序用時為fn,t0);64)A0=com;65)B0=mov;66)C0=t0;67)68)void bubblesort(SqList &L)/起泡排序69)70)start_t=clock();71)int i=1,j,com=0,mov=0;72)while(iL.length)73)74)for(j=1;jL.elemj+1.

13、key)78)79)L.elem0.key=L.elemj.key;80)L.elemj.key=L.elemj+1.key;81)L.elemj+1.key=L.elem0.key;82)mov+=3;83)84) 85) i+;86) 87) end_t=clock();88) printf( 比較次數(shù)為 %d移動次數(shù)為89) t1=(double)(end_t-start_t)/CLK_TCK;90) printf( 排序用時為 fn,t1);91) A1=com;92) B1=mov;93) C1=t1;94) 95) void InsertSort(SqList &L)/96) 97

14、) start_t=clock();98) int i,j,com=0,mov=0;99) for(i=2;i=L.length;i+)100) 101) if(L.elemi.keyL.elemi-1.key)102) 103) L.elem0.key=L.elemi.key;104) mov+;105) j=i-1;106) com+;107) while(L.elem0.keyL.elemj.key)108) 109) L.elemj+1.key=L.elemj.key;110) j-;111) mov+;112) com+;113) 114) L.elemj+1.key=L.elem0

15、.key;115) mov+;116) 117) 118) end_t=clock();119) printf(比較次數(shù)為%d移動次數(shù)為120) t2=(double)(end_t-start_t)/CLK_TCK;121) printf(排序用時為fn,t2);122) A2=com;123) B2=mov;124) C2=t2;125) 126) voidxier(SqList &L)/127) 128) start_t=clock();129) int i,d=L.length/2,j,w=0,k,com=0,mov=0;130) while(wd)%dn”,com,mov);直接插入排

16、序%dn”,com,mov);希爾排序131)132)w=1;133)for(i=w;iL.length;i=i+d)134)135)k=i;136)for(j=i+d;jL.elemj.key)139)140)k=j；141)com+;142)143)144)if(i!=k)145)146)L.elem0.key=L.elemi.key;147)L.elemi.key=L.elemk.key;148)L.elemk.key=L.elem0.key;149)mov+=3;150)151)w+;152)153)d=d154)w=1;155)156)end_t=clock();157)printf

17、(比較次數(shù)為%d移動次數(shù)為dn,com,mov);158)t3=(double)(end_t-start_t)/CLK_TCK;159)printf(排序用時為fn,t3);160)A3=com;161)B3=mov;162)C3=t3;163)164)void BeforeSort()165)166)yd1=0,bj1=0;167)168)void display(int m,int n)169)170)printf（比較次數(shù)為%d 移動次數(shù)為dn,m,n）;171)172)int Partition(SqList L,int low,int high)/快速排序173)174)int pi

18、votkey;175)L.elem0=L.elemlow;176)yd1+;177)pivotkey=L.elemlow.key;178)while (lowhigh)179)180)yd1+;181)while(low=pivotkey)182)183)-high;184)L.elemlow=L.elemhigh;185)bj1+;186)yd1+;187)188)while (lowhigh&L.elemlow.key=pivotkey)189)190)+low;191)L.elemhigh=L.elemlow;192)bj1+;193)yd1+;194)195)196)L.elemlow

19、=L.elem0;197)yd1+;198)return low;199)200)void QSort(SqList &L,int low,int high)201)202)int pivotloc;203)if(lowhigh)204)205)pivotloc=Partition(L,low,high);206)QSort(L,low,pivotloc-1);207)QSort(L,pivotloc+1,high);208)209)210)void QuickSort(SqList &L)211)212)start_t=clock();213)BeforeSort();214)QSort(L

20、,1,L.length);215)display(bj1,yd1);216)end_t=clock();217)t4=(double)(end_t-start_t)/CLK_TCK;218)printf(排序用時為%fn,t4);219)A4=bj1;220)B4=yd1;221)C4=t4;222)223)void Merge(ElemType R口,ElemType R1,int low,int m,int high) /歸并排序224)225)int i=low, j=m+1, k=low;226)while(i=m&j=high)227)228)if(Ri.key=Rj.key)229

21、)230)bj1+;231)R1k=Ri;232)yd1+;233)i+；234)k+;235)236)else237)238)bj1+;239)R1k=Rj;240)yd1+;241)j+;242)k+;243)244)245)while(i=m)246)247)R1k=Ri;248)yd1+;249)i+;250)k+;251)252)while(j=high)253)254)R1k=Rj;255)yd1+;256)j+;257)k+;258)259)260)void MergePass(ElemType R口,ElemType R1,int length, int n)261)262)i

22、nt i=0,j;263)while(i+2*length-1n)264)265)Merge(R,R1,i,i+length-1,i+2*length-1);266)i=i+2*length;267)268)if(i+length-1n-1)269)Merge(R,R1,i,i+length-1,n-1);270)else271)for(j=i;jn;j+)272)R1j=Rj；273)274)void MSort(ElemType R,ElemType R1,int n)275)276)int length=1;277)while (lengthn)278)279)MergePass(R,R

23、1,length,n);280)length=2*length;281)MergePass(R1,R,length,n);282)length=2*length;283)284)285)void MergeSort(SqList &L)286)287)start_t=clock();288)BeforeSort();289)MSort(L.elem,L.elem,L.length);290)display(bj1,yd1);291)end_t=clock();292)t5=(double)(end_t-start_t)/CLK_TCK;293)printf(排序用時為%fn,t5);294)A

24、5=bj1;295)B5=yd1;296)C5=t5;297)298)void printf(SqList &L)299)300)long int d6;301)int i,n;302)printf(n*比較次數(shù) *n);303)printf(n*n);304)for(i=0;i5;i+)305)di= sqrt (Ai/A5);306)printf(n歸并排序：*);307)printf(n*n);308)printf（選擇排序：）;309)for(n=0,i=0;n=di;n+)310)311)printf(*);312)313)printf(n*n);314)printf（冒泡排序：）；

25、315)for(n=0,i=1;n=di;n+)316)317)printf(*);318)319)printf(n*n);320)printf（直插排序：）;321)for(n=0,i=2;n=di;n+)322)323)printf(*);324)325)printf(n*n);326)printf（希爾排序：）;327)for(n=0,i=3;n=di;n+)328)329)printf(*);330)331)printf(n*n);332)printf（快排排序：）;333)for(n=0,i=4;n=di;n+)334)335)printf(*);336)337)printf(n*n

26、);338)printf(n移動次數(shù)339)printf(n*n);340)double e6;341)for(i=0;i6;i+)342)ei= sqrt (Bi/B3);343)printf(n希爾排序：*);344)printf(n*n);345)printf（選擇排序：）;346)for(n=0,i=0;n=ei;n+)347)348)printf(*);349)350)printf(n*n);351)printf（冒泡排序：）；352)for(n=0,i=1;n=ei;n+)353)354)printf(*);355)356)printf(n*n);357)printf（直插排序：）;358)for(n=0,i=2;n=ei;n+)359)360)printf(*);361)362)printf(n*n);363)printf（快排排序：）;364)for(n=0,i=4;n=ei;n+)n)；365)366)printf(*);367)368)printf(n*n);369)printf（歸并排序：）；370)for(n=0,i=5;n=ei;n+)371)372)printf(*);373)374)printf(n*n)