數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)_各種排序算法時間性能的比較

1、學(xué) 號 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說明書題目各種排序算法時間性能的比較起止日期： 2011年 12月 12 日 至 2011 年 12月16日學(xué)生姓名班級成績指導(dǎo)教師(簽字) 電子與信息工程系2011年 12月16日天津城市建設(shè)學(xué)院課程設(shè)計(jì)任務(wù)書20112012學(xué)年第1學(xué)期 電子與信息工程 系 軟件工程 專業(yè) 班級課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目： 各種排序算法時間性能的比較 完成期限：自 2011 年 12 月 12 日至 2011 年 12 月 16 日共 1 周設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁）：一、設(shè)計(jì)目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運(yùn)算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實(shí)際問題。二、設(shè)

2、計(jì)要求 （1）重視課程設(shè)計(jì)環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實(shí)的工作態(tài)度對待課程設(shè)計(jì)的每一項(xiàng)任務(wù)；（2）按照課程設(shè)計(jì)的題目要求，獨(dú)立地完成各項(xiàng)任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計(jì)入本課程設(shè)計(jì)成績。凡發(fā)現(xiàn)實(shí)驗(yàn)報告或源程序雷同，涉及的全部人員皆以零分計(jì)入本課程設(shè)計(jì)成績；（3）學(xué)生在接受設(shè)計(jì)任務(wù)后，首先要按設(shè)計(jì)任務(wù)書的要求編寫設(shè)計(jì)進(jìn)程表；（4）認(rèn)真編寫課程設(shè)計(jì)報告。三、設(shè)計(jì)內(nèi)容對各種排序方法（直接插入排序、希爾排序、起泡排序、快速排序、直接選擇排序、堆排序和歸并排序）的時間性能進(jìn)行比較。(1) 設(shè)計(jì)并實(shí)現(xiàn)上述各種排序算法；(2) 產(chǎn)生正序和逆序的初始排列分別調(diào)用上述排序算法，并比較時間性能；(

3、3) 產(chǎn)生隨機(jī)的初始排列分別調(diào)用上述排序算法，并比較時間性能。四、參考文獻(xiàn)1王紅梅數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社2王紅梅數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)清華大學(xué)出版社3嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社一、需求分析需要對用戶輸入的一組數(shù)據(jù)進(jìn)行排序，并對7種排序的正逆排序進(jìn)行分析，并做出時間復(fù)雜度的比較，并得出最優(yōu)的排序方法作為結(jié)果。二、問題求解在排序時，開始做出的任何一個排序的的逆排序的時間復(fù)雜度都是一個定值不會變，后來經(jīng)過單步調(diào)試，發(fā)現(xiàn)是把正排序放在了起之前，所以逆排序排出來的都是已經(jīng)排好的數(shù)據(jù)，所以不會變，我通過復(fù)制數(shù)組，做成了兩個數(shù)組（最后做成的總程序?yàn)槎鄠€數(shù)組），然后分別對應(yīng)每個算法做

4、排序。這樣就不會在顯示后一個算法的排序是前一個算法已經(jīng)排序好的數(shù)組，而是用戶輸入的原始數(shù)組。一下是對于每個排序的分析及所遇見的問題：（排序解釋都用正排序說明）1冒泡排序該排序沒有什么打的問題，用兩個for循環(huán)即可做出排序。排序原理是兩兩對比大的放前，小的放后。2插入排序該排序是以第n個數(shù)（需排序的數(shù)）直接去與數(shù)組里已經(jīng)排序好的數(shù)做比較。將其插入比它大的數(shù)之前，比它小的數(shù)之后。在做該數(shù)組的時候我之前以為r0的哨兵可以用任意一的變量來代替，從而是數(shù)組從r0開始計(jì)數(shù)，結(jié)果表明，并不是這樣，因?yàn)槊恳淮?，最小的?shù)都會唄覆蓋掉，所以原假設(shè)不成立。3希爾排序：先把數(shù)組分成等長的兩個數(shù)組，用ri與rn/2+i

5、做比較曉得在前，打的在后，然后在一剛剛兩兩一組的兩組做比較，就這樣，每次比較，每組數(shù)的個數(shù)都是上一次的兩倍，最后完成整個數(shù)組的排序。4直接選擇排序該排序是現(xiàn)在無序的數(shù)組中找最值，然后作為第一個元素，之后就是每次找最值，作為下一個元素，直至最后一個元素，排序完成。5快速排序定義兩個指針，分別只想第一個與最后一個元素，這兩個元素做比較，大的放前，小的放后，然后移動指針，進(jìn)行下一個比較。兩次這樣比較排序以后，數(shù)組變成為了有序數(shù)列。該算法采用為遞歸算法。6歸并排序該排序，也是需要調(diào)用遞歸。先把數(shù)組對半分多次，直到每組只有兩個數(shù)據(jù)時，進(jìn)行對比、排序。然后再兩兩合并，最后做到整個數(shù)組的排序完成7堆排序先是

6、對堆做比較，左子數(shù)小于本數(shù)，右子數(shù)大于本數(shù)，然后不停比較，交換，最后達(dá)到整個數(shù)組的排序。三、總體設(shè)計(jì)每一個排序都給出排序后的數(shù)組及本排序的時間復(fù)雜度。主程序快速排序冒泡排序插入排序希爾排序直接選擇排序歸并排序堆排序主程序快速排序冒泡排序插入排序希爾排序直接選擇排序歸并排序堆排序雜亂數(shù)組輸出整理排序數(shù)組，并作出分析，得到最有方法四、詳細(xì)設(shè)計(jì)/冒泡排序void Zmppx(int a ,int n ) /正序排序void Nmppx(int a ,int n ) /逆序排序/插入排序void Zcrpx(int r ,int n) /正序排序void Ncrpx(int r ,int n) /逆序

7、排序/希爾排序void Zxepx(int r ,int n) /正序排序void Nxepx(int r ,int n) /逆序排序/直接選擇排序void Zzjxzpx(int r ,int n) /正序排序void Nzjxzpx(int r ,int n) /逆序排序/快速排序void Zkspx(int r,int left,int right) /正序排序void Nkspx(int r,int left,int right) /逆序排序/歸并排序void Copy(int r,int b,int l,int g) /復(fù)制函數(shù)void ZMerge(int c,int d,int

8、l,int m,int g) /正排序算法void Zgbpx(int r,int left,int right) /正序排序void NMerge(int c,int d,int l,int m,int g) /逆排序算法void Ngbpx(int r,int left,int right) /逆序排序/堆排序void Zsift(int r,int k,int m) /篩選法調(diào)整堆算法（正）void Zdpx(int r ,int n) /正序排序void Nsift(int r,int k,int m) /篩選法調(diào)整堆算法（逆）void Ndpx(int r ,int n) /逆序排序

9、/主函數(shù)void main() /輸入輸出五、調(diào)試與測試調(diào)試用的是簡單的黑盒測試，輸入數(shù)據(jù)，給出結(jié)果。遇到的問題如“二”所示。六、關(guān)鍵源程序清單和執(zhí)行結(jié)果源程序：#include using namespace std;int mpzl=0,mpnl=0;int crzl=0,crnl=0;int xezl=0,xenl=0;int zjzl=0,zjnl=0;int kszl=0,ksnl=0;int gbzl=0,gbnl=0;int dzl=0,dnl=0;/*/冒泡排序void Zmppx(int a ,int n )for(int t=1;t=n;t+)for(int k=1 ;ka

10、k+1)int p=ak+1;ak+1=ak;ak=p;mpzl+;mpzl+;mpzl+;void Nmppx(int a ,int n )for(int t=1;t0;k-)if(akak+1)int p=ak+1;ak+1=ak;ak=p;mpnl+;mpnl+;mpnl+;/*/插入排序void Zcrpx(int r ,int n)for(int i=2; ir0;j-)rj+1=rj;crzl+;rj+1=r0;crzl+;void Ncrpx(int r ,int n)for(int i=2; i=n ; i+)r0=ri;for( int j=i-1;rj=1; d=d/2)f

11、or(int i=d+1; i0 &r0=1; d=d/2)for(int i=d+1; i0 &r0rj;j=j-d)rj+d=rj;xenl+;rj+d=r0;xenl+;xenl+;/*/直接選擇排序void Zzjxzpx(int r ,int n)for(int i=1; in ; i+)int m=i;for(int j=i+1;j=n;j+)if(rjrm)m=j;zjzl+;int p;if(n!=i)p=ri;ri=rm;rm=p;zjzl+;zjzl+;void Nzjxzpx(int r ,int n)for(int i=1; in ; i+)int m=i;for(in

12、t j=i+1;jrm)m=j;zjnl+;int p;if(n!=i)p=ri;ri=rm;rm=p;zjnl+;zjnl+;/*/快速排序void Zkspx(int r,int left,int right)int i=left,j=right,p=rleft; while(ij)while(i=p)j-;kszl+;int m=ri;ri=rj; rj=m;kszl+;while(ij&ri=p)i+;kszl+;m=rj;rj=ri;ri=m;kszl+; if(lefti+1) Zkspx(r,i+1,right);void Nkspx(int r,int left,int rig

13、ht)int i=left,j=right,p=rleft; while(ij)while(ij&rj=p)j-;ksnl+;int m=ri;ri=rj; rj=m;ksnl+;while(i=p)i+;m=rj;rj=ri;ri=m;ksnl+; if(lefti+1) Nkspx(r,i+1,right);/*/歸并排序int b100;/定義全局變量，存儲Merge合并時暫時存放排序后的數(shù)組元素/真正的排序函數(shù) 比較左右兩段元素 將較小數(shù)字依次暫存數(shù)組b中/將數(shù)組b暫存的排序后的元素返回?cái)?shù)組void Copy(int r,int b,int l,int g)for(int i=l;i=

14、g;i+)ri=bi;gbzl+;gbnl+;/正序合并void ZMerge(int c,int d,int l,int m,int g)int i=l,j=m+1,k=l;while(i=m)&(j=g)if(cim)for(int q=j;q=g;q+)dk+=cq;gbzl+;elsefor(int q=i;q=m;q+)dk+=cq;gbzl+;/正序合并排序主函數(shù)void Zgbpx(int r,int left,int right)if(leftright)int i=(left+right)/2; /數(shù)組均分成兩段Zgbpx(r,left,i); /遞歸對左邊數(shù)據(jù)進(jìn)行合并排序Z

15、gbpx(r,i+1,right); /遞歸對右邊數(shù)據(jù)進(jìn)行合并排序ZMerge(r,b,left,i,right); /調(diào)用排序函數(shù)Copy(r,b,left,right);/逆序合并void NMerge(int c,int d,int l,int m,int g)int i=l,j=m+1,k=l;while(i=m)&(j=cj)dk+=ci+;gbnl+;elsedk+=cj+;gbnl+;if(im)for(int q=j;q=g;q+)dk+=cq;gbnl+;elsefor(int q=i;q=m;q+)dk+=cq;gbnl+;/逆序合并排序主函數(shù)void Ngbpx(int

16、r,int left,int right)if(leftright)int i=(left+right)/2; /數(shù)組均分成兩段Ngbpx(r,left,i); /遞歸對左邊數(shù)據(jù)進(jìn)行合并排序Ngbpx(r,i+1,right); /遞歸對右邊數(shù)據(jù)進(jìn)行合并排序NMerge(r,b,left,i,right); /調(diào)用排序函數(shù)Copy(r,b,left,right);/*/堆排序void Zsift(int r,int k,int m)int i=k;int j=2*i;while(j=m)if(jm & rjrj)dzl+;break;elseint p=ri;ri=rj;rj=p;dzl+;i

17、=j;j=2*i;void Zdpx(int r ,int n)for(int i=n/2; i=1 ; i-)dzl+;Zsift(r,i,n);for(i=1; in;i+)int p=r1;r1=rn-i+1;rn-i+1=p;dzl+;Zsift(r,1,n-i);void Nsift(int r,int k,int m)int i=k;int j=2*i;while(j=m)if(jrj+1)j+;dnl+;if(ri=1 ; i-)dnl+;Nsift(r,i,n);for(i=1; in;i+)int p=r1;r1=rn-i+1;rn-i+1=p;dnl+;Nsift(r,1,

18、n-i);/*void main()int r1000,mr11000,cr11000,xr11000,zr11000,kr11000,gr11000,dr11000,mr21000,cr21000,xr21000,zr21000,kr21000,gr21000,dr21000;int n;cout請輸入排序個數(shù)n;cout請輸入n個要排序的數(shù)整數(shù)endl;for(int i=1;iri;for(int k=1;k=n;k+)mr1k=rk;mr2k=rk;cr1k=rk;cr2k=rk;xr1k=rk;xr2k=rk;zr1k=rk;zr2k=rk;kr1k=rk;kr2k=rk;gr1k=

19、rk;gr2k=rk;dr1k=rk;dr2k=rk;Zmppx(mr1,n);cout正序排序以后為endl;for(int j=1;j=n;j+)coutmr1jt;coutendl;Nmppx(mr2,n);cout逆序排序以后為endl;for( j=1;j=n;j+)coutmr2jt;coutendl;Zcrpx(cr1,n);Ncrpx(cr2,n);Zxepx(xr1,n);Nxepx(xr2,n);Zzjxzpx(zr1,n);Nzjxzpx(zr2,n);Zkspx(kr1,1,n);Nkspx(kr2,1,n);Zgbpx(gr1,1,n);Ngbpx(gr2,1,n);

20、Zdpx(dr1,n);Ndpx(dr2,n);cout冒泡正序排序時間復(fù)雜度為mpzl次endl;cout冒泡逆序排序時間復(fù)雜度為mpnl次endl;cout*endl;cout插入正序排序時間復(fù)雜度為crzl次endl;cout插入逆序排序時間復(fù)雜度為crnl次endl;cout*endl;cout希爾正序排序時間復(fù)雜度為xezl次endl;cout希爾逆序排序時間復(fù)雜度為xenl次endl;cout*endl;cout直接選擇正序排序時間復(fù)雜度為zjzl次endl;cout直接選擇逆序排序時間復(fù)雜度為zjnl次endl;cout*endl;cout快速正序排序時間復(fù)雜度為kszl次end

21、l;cout快速逆序排序時間復(fù)雜度為ksnl次endl;cout*endl;cout歸并正序排序時間復(fù)雜度為gbzl次endl;cout歸并逆序排序時間復(fù)雜度為gbnl次endl;cout*endl;cout堆正序排序時間復(fù)雜度為dzl次endl;cout堆逆序排序時間復(fù)雜度為dnl次endl;cout*endl;int p;if(mpzl=crzl & mpzl=xezl & mpzl=zjzl & mpzl=kszl & mpzl=gbzl & mpzl=dzl)p=1;if(crzlmpzl & crzl=xezl & crzl=zjzl & crzl=kszl & crzl=gbzl

22、& crzl=dzl)p=2;if(xezlmpzl & xezlcrzl & xezl=zjzl & xezl=kszl & xezl=gbzl & xezl=dzl)p=3;if(zjzlmpzl & zjzlcrzl & zjzlxezl & zjzl=kszl & zjzl=gbzl & zjzl=dzl)p=4;if(kszlmpzl & kszlcrzl & kszlxezl & kszlzjzl & kszl=gbzl & kszl=dzl)p=5;if(gbzlmpzl & gbzlcrzl & gbzlxezl & gbzlzjzl & gbzlkszl & gbzl=dzl

23、)p=6;if(dzlmpzl & dzlcrzl & dzlxezl & dzlzjzl & dzlkszl & dzlgbzl)p=7;switch(p)case 1:cout該數(shù)列正排序使用冒泡排序最為簡便endl;break;case 2:cout該數(shù)列正排序使用插入排序最為簡便endl;break;case 3:cout該數(shù)列正排序使用希爾排序最為簡便endl;break;case 4:cout該數(shù)列正排序使用直接選擇排序最為簡便endl;break;case 5:cout該數(shù)列正排序使用快速排序最為簡便endl;break;case 6:cout該數(shù)列正排序使用歸并排序最為簡便endl;break;case 7:cout該數(shù)列正排序使用堆排序最為簡便endl;break;int q;if(mpnl=crnl