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

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

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

3、分別調(diào)用上述排序算法，并比擬時(shí)間性能。四、參考文獻(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é)出版社一、需求分析需要對(duì)用戶輸入的一組數(shù)據(jù)進(jìn)行排序，并對(duì)7種排序的正逆排序進(jìn)行分析，并做出時(shí)間復(fù)雜度的比擬，并得出最優(yōu)的排序方法作為結(jié)果。二、問題求解在排序時(shí)，開始做出的任何一個(gè)排序的的逆排序的時(shí)間復(fù)雜度都是一個(gè)定值不會(huì)變，后來經(jīng)過單步調(diào)試，發(fā)現(xiàn)是把正排序放在了起之前，所以逆排序排出來的都是已經(jīng)排好的數(shù)據(jù)，所以不會(huì)變，我通過復(fù)制數(shù)組，做成了兩個(gè)數(shù)組最后做成的總程序?yàn)槎鄠€(gè)數(shù)組，然后分別對(duì)應(yīng)每個(gè)算法做排序。這樣就不會(huì)在顯示后一個(gè)算法

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

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

6、數(shù)，然后不停比擬，交換，最后到達(dá)整個(gè)數(shù)組的排序。三、總體設(shè)計(jì)每一個(gè)排序都給出排序后的數(shù)組及本排序的時(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) /逆序排序/希爾排序void Zxepx(in

7、t 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 l,int m,int g) /正排序算

8、法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) /逆序排序/主函數(shù)void main() /輸入輸出五、調(diào)

9、試與測(cè)試調(diào)試用的是簡(jiǎn)單的黑盒測(cè)試，輸入數(shù)據(jù)，給出結(jié)果。遇到的問題如“二所示。六、關(guān)鍵源程序清單和執(zhí)行結(jié)果源程序：#include <iostream>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 ;k<n;

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

11、crzl+;void Ncrpx(int r ,int n)for(int i=2; i<=n ; i+)r0=ri;for( int j=i-1;rj<r0;j-)rj+1=rj;crnl+;rj+1=r0;crnl+;/*/希爾排序void Zxepx(int r ,int n)for(int d=n/2; d>=1; d=d/2)for(int i=d+1; i<=n; i+)r0=ri;for(int j=i-d;j>0 &&r0<rj;j=j-d)rj+d=rj;xezl+;rj+d=r0;xezl+;xezl+;void Nxep

12、x(int r ,int n)for(int d=n/2; d>=1; d=d/2)for(int i=d+1; i<=n; i+)r0=ri;for(int j=i-d;j>0 &&r0>rj;j=j-d)rj+d=rj;xenl+;rj+d=r0;xenl+;xenl+;/*/直接選擇排序void Zzjxzpx(int r ,int n)for(int i=1; i<n ; i+)int m=i;for(int j=i+1;j<=n;j+)if(rj<rm)m=j;zjzl+;int p;if(n!=i)p=ri;ri=rm;rm

13、=p;zjzl+;zjzl+;void Nzjxzpx(int r ,int n)for(int i=1; i<n ; i+)int m=i;for(int j=i+1;j<=n;j+)if(rj>rm)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(i<j)while(i<j&&rj>=p)j-;kszl+;int m=ri;ri=r

14、j; rj=m;kszl+;while(i<j&&ri<=p)i+;kszl+;m=rj;rj=ri;ri=m;kszl+; if(left<i-1) Zkspx(r,left,i-1); if(right>i+1) Zkspx(r,i+1,right);void Nkspx(int r,int left,int right)int i=left,j=right,p=rleft; while(i<j)while(i<j&&rj<=p)j-;ksnl+;int m=ri;ri=rj; rj=m;ksnl+;while(i&

15、lt;j&&ri>=p)i+;m=rj;rj=ri;ri=m;ksnl+; if(left<i-1) Nkspx(r,left,i-1); if(right>i+1) Nkspx(r,i+1,right);/*/歸并排序int b100;/定義全局變量，存儲(chǔ)Merge合并時(shí)暫時(shí)存放排序后的數(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<=g;i+)ri=bi;gbzl+;gbnl+;/正序合并void

16、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(ci<=cj)dk+=ci+;gbzl+;elsedk+=cj+;gbzl+;if(i>m)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(left<right)int i=(left+right)

17、/2; /數(shù)組均分成兩段Zgbpx(r,left,i); /遞歸對(duì)左邊數(shù)據(jù)進(jìn)行合并排序Zgbpx(r,i+1,right); /遞歸對(duì)右邊數(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<=g)if(ci>=cj)dk+=ci+;gbnl+;elsedk+=cj+;gbnl+;if(i>m)for(int q=j;q<

18、;=g;q+)dk+=cq;gbnl+;elsefor(int q=i;q<=m;q+)dk+=cq;gbnl+;/逆序合并排序主函數(shù)void Ngbpx(int r,int left,int right)if(left<right)int i=(left+right)/2; /數(shù)組均分成兩段Ngbpx(r,left,i); /遞歸對(duì)左邊數(shù)據(jù)進(jìn)行合并排序Ngbpx(r,i+1,right); /遞歸對(duì)右邊數(shù)據(jù)進(jìn)行合并排序NMerge(r,b,left,i,right); /調(diào)用排序函數(shù)Copy(r,b,left,right);/*/堆排序void Zsift(int r,int k

19、,int m)int i=k;int j=2*i;while(j<=m)if(j<m && rj<rj+1)j+;dzl+;if(ri>rj)dzl+;break;elseint p=ri;ri=rj;rj=p;dzl+;i=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; i<n;i+)int p=r1;r1=rn-i+1;rn-i+1=p;dzl+;Zsift(r,1,n-i);void Nsift(int r,int k,

20、int m)int i=k;int j=2*i;while(j<=m)if(j<m && rj>rj+1)j+;dnl+;if(ri<rj)dnl+;break;elseint p=ri;ri=rj;rj=p;dnl+;i=j;j=2*i;void Ndpx(int r ,int n)for(int i=n/2; i>=1 ; i-)dnl+;Nsift(r,i,n);for(i=1; i<n;i+)int p=r1;r1=rn-i+1;rn-i+1=p;dnl+;Nsift(r,1,n-i);/*void main()int r1000,m

21、r11000,cr11000,xr11000,zr11000,kr11000,gr11000,dr11000,mr21000,cr21000,xr21000,zr21000,kr21000,gr21000,dr21000;int n;cout<<"請(qǐng)輸入排序個(gè)數(shù)"<<endl;cin>>n;cout<<"請(qǐng)輸入"<<n<<"個(gè)要排序的數(shù)整數(shù)"<<endl;for(int i=1;i<=n;i+)cin>>ri;for(int k=1;

22、k<=n;k+)mr1k=rk;mr2k=rk;cr1k=rk;cr2k=rk;xr1k=rk;xr2k=rk;zr1k=rk;zr2k=rk;kr1k=rk;kr2k=rk;gr1k=rk;gr2k=rk;dr1k=rk;dr2k=rk;Zmppx(mr1,n);cout<<"正序排序以后為"<<endl;for(int j=1;j<=n;j+)cout<<mr1j<<"t"cout<<endl;Nmppx(mr2,n);cout<<"逆序排序以后為"

23、;<<endl;for( j=1;j<=n;j+)cout<<mr2j<<"t"cout<<endl;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);Zdpx(dr1,n);Ndpx(dr2,n);cout<<"冒泡正序排序時(shí)間復(fù)雜度為"<<mp

24、zl<<"次"<<endl;cout<<"冒泡逆序排序時(shí)間復(fù)雜度為"<<mpnl<<"次"<<endl;cout<<"*"<<endl;cout<<"插入正序排序時(shí)間復(fù)雜度為"<<crzl<<"次"<<endl;cout<<"插入逆序排序時(shí)間復(fù)雜度為"<<crnl<<"

25、次"<<endl;cout<<"*"<<endl;cout<<"希爾正序排序時(shí)間復(fù)雜度為"<<xezl<<"次"<<endl;cout<<"希爾逆序排序時(shí)間復(fù)雜度為"<<xenl<<"次"<<endl;cout<<"*"<<endl;cout<<"直接選擇正序排序時(shí)間復(fù)雜度為"&l

26、t;<zjzl<<"次"<<endl;cout<<"直接選擇逆序排序時(shí)間復(fù)雜度為"<<zjnl<<"次"<<endl;cout<<"*"<<endl;cout<<"快速正序排序時(shí)間復(fù)雜度為"<<kszl<<"次"<<endl;cout<<"快速逆序排序時(shí)間復(fù)雜度為"<<ksnl<

27、<"次"<<endl;cout<<"*"<<endl;cout<<"歸并正序排序時(shí)間復(fù)雜度為"<<gbzl<<"次"<<endl;cout<<"歸并逆序排序時(shí)間復(fù)雜度為"<<gbnl<<"次"<<endl;cout<<"*"<<endl;cout<<"堆正序排序時(shí)間復(fù)雜度為&

28、quot;<<dzl<<"次"<<endl;cout<<"堆逆序排序時(shí)間復(fù)雜度為"<<dnl<<"次"<<endl;cout<<"*"<<endl;int p;if(mpzl<=crzl && mpzl<=xezl && mpzl<=zjzl && mpzl<=kszl && mpzl<=gbzl &&

29、; mpzl<=dzl)p=1;if(crzl<mpzl && crzl<=xezl && crzl<=zjzl && crzl<=kszl && crzl<=gbzl && crzl<=dzl)p=2;if(xezl<mpzl && xezl<crzl && xezl<=zjzl && xezl<=kszl && xezl<=gbzl && xezl<=dz

30、l)p=3;if(zjzl<mpzl && zjzl<crzl && zjzl<xezl && zjzl<=kszl && zjzl<=gbzl && zjzl<=dzl)p=4;if(kszl<mpzl && kszl<crzl && kszl<xezl && kszl<zjzl && kszl<=gbzl && kszl<=dzl)p=5;if(gbzl<

31、mpzl && gbzl<crzl && gbzl<xezl && gbzl<zjzl && gbzl<kszl && gbzl<=dzl)p=6;if(dzl<mpzl && dzl<crzl && dzl<xezl && dzl<zjzl && dzl<kszl && dzl<gbzl)p=7;switch(p)case 1:cout<<"該數(shù)列

32、正排序使用冒泡排序最為簡(jiǎn)便"<<endl;break;case 2:cout<<"該數(shù)列正排序使用插入排序最為簡(jiǎn)便"<<endl;break;case 3:cout<<"該數(shù)列正排序使用希爾排序最為簡(jiǎn)便"<<endl;break;case 4:cout<<"該數(shù)列正排序使用直接選擇排序最為簡(jiǎn)便"<<endl;break;case 5:cout<<"該數(shù)列正排序使用快速排序最為簡(jiǎn)便"<<endl;br

33、eak;case 6:cout<<"該數(shù)列正排序使用歸并排序最為簡(jiǎn)便"<<endl;break;case 7:cout<<"該數(shù)列正排序使用堆排序最為簡(jiǎn)便"<<endl;break;int q;if(mpnl<=crnl && mpnl<=xenl && mpnl<=zjnl && mpnl<=ksnl && mpnl<=gbnl && mpnl<=dnl)q=1;if(crnl<mpn

34、l && crnl<=xenl && crnl<=zjnl && crnl<=ksnl && crnl<=gbnl && crnl<=dnl)q=2;if(xenl<mpnl && xenl<crnl && xenl<=zjnl && xenl<=ksnl && xenl<=gbnl && xenl<=dnl)q=3;if(zjnl<mpnl &&

35、zjnl<crnl && zjnl<xenl && zjnl<=ksnl && zjnl<=gbnl && zjnl<=dnl)q=4;if(ksnl<mpnl && ksnl<crnl && ksnl<xenl && ksnl<zjnl && ksnl<=gbnl && ksnl<=dnl)p=5;if(gbnl<mpnl && gbnl<crnl &

36、;& gbnl<xenl && gbnl<zjnl && gbnl<ksnl && gbnl<=dnl)q=6;if(dnl<mpnl && dnl<crnl && dnl<xenl && dnl<zjnl && dzl<ksnl && dnl<gbnl)q=7;switch(q)case 1:cout<<"該數(shù)列逆排序使用冒泡排序最為簡(jiǎn)便"<<endl;b

37、reak;case 2:cout<<"該數(shù)列逆排序使用插入排序最為簡(jiǎn)便"<<endl;break;case 3:cout<<"該數(shù)列逆排序使用希爾排序最為簡(jiǎn)便"<<endl;break;case 4:cout<<"該數(shù)列逆排序使用直接選擇排序最為簡(jiǎn)便"<<endl;break;case 5:cout<<"該數(shù)列逆排序使用快速排序最為簡(jiǎn)便"<<endl;break;case 6:cout<<"該數(shù)列逆排序使用歸并排序最為簡(jiǎn)便"<<endl;break;case 7:cout<<"該數(shù)列逆排序使用堆排序最為簡(jiǎn)便"<<endl;break;運(yùn)算結(jié)果碩士論文 是碩士研究生所撰寫的學(xué)術(shù)論文，具有一定的理論深度和更高的學(xué)術(shù)水平，更加強(qiáng)調(diào)作者思想觀點(diǎn)的獨(dú)創(chuàng)性，以及研究成果應(yīng)具備更強(qiáng)的實(shí)用價(jià)值和更高的科學(xué)價(jià)值。碩士論文是碩士研究生所撰寫的學(xué)術(shù)論文。優(yōu)秀的碩士論文能夠反映出作者對(duì)所學(xué)習(xí)專業(yè)的理論知識(shí)掌握的程度和水平，能夠幫助作者構(gòu)建起