數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法比較

1、 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程設(shè)計(jì)報(bào)告 題目： 排序算法比較 學(xué)生姓名： 汪洪 學(xué) 號(hào)： 201120181805 班 級(jí)： 1121822 指導(dǎo)教師： 周華清 2013年1月10日目錄需求分析··································&#

2、183;·····3總體設(shè)計(jì)········································4詳細(xì)設(shè)計(jì)··

3、3;·····································5類的設(shè)計(jì)············

4、;·······················5現(xiàn)實(shí)部分··························

5、··············8隨機(jī)數(shù)賦值·································8結(jié)果輸出·&

6、#183;·································8直接插入排序···············

7、················9冒泡排序·································&

8、#183;·10選擇排序···································11快速排序···········&

9、#183;·······················13堆排序·························&#

10、183;···········15二路歸并排序·······························18程序測(cè)試·····

11、···································21總結(jié)··············&#

12、183;·····························251 需求分析本程序主要為了實(shí)現(xiàn)對(duì)各排序算法的性能比較。主要包括對(duì)直接插入排序，冒泡排序，選擇排序，快速排序，堆排序二路歸并排序六種排序算法在時(shí)間復(fù)雜度上的性能比較?；诖四康男枰O(shè)定一個(gè)順序表來(lái)產(chǎn)生一組數(shù)據(jù)，本程序用了一個(gè)長(zhǎng)度為30000的

13、long int型數(shù)組并用了以時(shí)間為隨機(jī)種子產(chǎn)生了一組數(shù)組。用六個(gè)模塊來(lái)實(shí)現(xiàn)各種排序功能并在各模塊中完成計(jì)算排序所用的時(shí)間。并用一個(gè)數(shù)組保存各種排序所用的時(shí)間。為了比較各種排序的在時(shí)間上的優(yōu)劣性將各個(gè)排序所用的時(shí)間進(jìn)行比較并輸出結(jié)果！2 總體設(shè)計(jì)Switch結(jié)構(gòu)設(shè)定long數(shù)組開(kāi)始 進(jìn)行快速排序進(jìn)行冒泡排序進(jìn)行冒泡排序進(jìn)行選擇排序 二路歸并排序堆排序冒泡排序直接插入排序快速排序選擇排序 保存所需時(shí)間進(jìn)行二路歸并排序進(jìn)行堆排序進(jìn)行選擇排序進(jìn)行直接插入排序 結(jié)束對(duì)所有排序的時(shí)間進(jìn)行從小到大的排序并輸出結(jié)果獲得所有排序所花費(fèi)的時(shí)間（包括未switch結(jié)構(gòu)中未被選中的排序）保存所需時(shí)間保存所需時(shí)間保存

14、所需時(shí)間保存所需時(shí)間保存所需時(shí)間 3 詳細(xì)設(shè)計(jì)1. 類的設(shè)計(jì)本程序功能只是為了比較各種排序算法在時(shí)間上的優(yōu)劣。所以可以用一個(gè)類來(lái)完成的有的操作，固本程序只需定義一個(gè)類。為實(shí)現(xiàn)本程序功能定義一個(gè)類其中包括了一個(gè)長(zhǎng)度300000的數(shù)組。并且為了實(shí)現(xiàn)各種排序功能應(yīng)當(dāng)設(shè)計(jì)功能函數(shù)分別實(shí)現(xiàn)各種類型的排序和排序后的結(jié)果。以下對(duì)這個(gè)類進(jìn)行詳細(xì)說(shuō)明。類名：sortrather數(shù)據(jù)成員：long int aN 其中N為一個(gè)全局常量其值為30000，該成員用來(lái)保存一個(gè)用于保存一組數(shù)據(jù)用于排序。Long int time6該數(shù)組用于保存各種排序所用的時(shí)間，以便對(duì)種種排序所用時(shí)間進(jìn)行比較。成員函數(shù)：1. void p

15、ubction（）實(shí)現(xiàn)功能：本函數(shù)的的作用是給數(shù)據(jù)成員 aN進(jìn)行隨機(jī)賦值。實(shí)現(xiàn)算法：用系統(tǒng)時(shí)間作為隨機(jī)種子。再將隨機(jī)函數(shù)對(duì)90000的取余賦給。aN.2. print()實(shí)現(xiàn)功能：將aN的前30個(gè)元素輸出。實(shí)現(xiàn)算法：將數(shù)組元素一個(gè)一個(gè)的輸出。3.void insertsort()實(shí)現(xiàn)功能：以直接插入排序算法完成對(duì)數(shù)組a的直接插入排序。實(shí)現(xiàn)算法：以當(dāng)前元素以基準(zhǔn)元素，將后面的元素與其進(jìn)行比較。如果比當(dāng)前元素大則直接插到當(dāng)前元素后面。否則把當(dāng)前元素后移并置當(dāng)前元素為前一個(gè)元素。重復(fù)此步驟。4void bubblesort()實(shí)現(xiàn)功能：以冒泡的方式對(duì)數(shù)組aN進(jìn)行排序。實(shí)現(xiàn)算法：從第N-1個(gè)數(shù)開(kāi)始與前

16、一個(gè)數(shù)比較使之小的在的前大的在后，直到第1個(gè)數(shù)，這樣便找到了最小的用同樣的方法找到第二小的數(shù)······。3. void selectsort(long int a,long int n)實(shí)現(xiàn)功能：以選擇排序的方法完成對(duì)aN的排序。實(shí)現(xiàn)算法：依次取數(shù)組aN中的第一個(gè)、第二個(gè)······到第aN個(gè)，與數(shù)組中它所在位置后的其它元素進(jìn)行比較并使a1,a2,.aN取余下元素的最小值。4. void quick(long int a,long int left,long int rig

17、ht)實(shí)現(xiàn)功能：用快遞排序的方法來(lái)實(shí)現(xiàn)對(duì)aN從小到大的排序?qū)崿F(xiàn)算法：先取a1作為基準(zhǔn)點(diǎn)從a-1開(kāi)始依次與基準(zhǔn)點(diǎn)比較若a1大于其中的某個(gè)數(shù)則交換a1與這個(gè)數(shù)的值。并以該數(shù)為基準(zhǔn)點(diǎn)從a2開(kāi)始從復(fù)以上步驟真以基準(zhǔn)點(diǎn)為界兩邊的數(shù)大小被分開(kāi)。再對(duì)分好區(qū)間執(zhí)行此步驟。5.void heapsort(long int a);實(shí)現(xiàn)功能：用堆排序?qū)?shù)組aN進(jìn)行排序。實(shí)現(xiàn)算法：從N/2開(kāi)始雙數(shù)組進(jìn)行移位使得對(duì)于數(shù)組中滿足ai>a2*i,ai>a2*i+1.6. void mergesort(long int a);實(shí)現(xiàn)功能：用二路歸并排序?qū)?shù)組aN進(jìn)行排序。實(shí)現(xiàn)算法：先以N/2為間隔對(duì)數(shù)組aN進(jìn)行直接

18、插入排序。依次使N=N/2縮小間隔。最終作一次直接插入排序。實(shí)現(xiàn)部分對(duì)數(shù)組隨機(jī)賦值void pubction()srand(time(NULL);for(long int i=0;i<N;i+) ai=rand()%90000;輸出數(shù)組前30個(gè)元素void print(long int a)int i;for(i=0;i<W;i+)cout<<ai<<"t"cout<<endl;直接插入排序void insertsort(long int a)long int i,j,temp;pubction(a);/cout<<

19、;"初始數(shù)組是：n" /print(a);for(i=1;i<N;i+)temp=ai;for(j=i-1;j>=0;j-)if(temp<aj)ppp0+;aj+1=aj;elsebreak;aj+1=temp;/cout<<"直接排序后的數(shù)組是：n"/print(a);cout<<"直接插入排序耗時(shí)： "<<ppp0/100000<<"毫秒"<<endl;冒泡排序void bubblesort(long int a)long int

20、i,j,temp;pubction(a);/cout<<"初始數(shù)組是：n"/print(a);for(i=0;i<N;i+)for(j=N-1;j>i;j-)if(aj<aj-1)ppp1+;temp=aj;aj=aj-1;aj-1=temp;/cout<<"冒泡排序后的數(shù)組是：n"/print(a);cout<<"冒泡排序耗時(shí)為： "<<ppp1/100000<<"毫秒"<<endl;選擇排序void selectsort(

21、long int a,long int n)long int i,j,temp,k;char trtemp40,trt40;if(n>6)pubction(a);for(i=0;i<n-1;i+)temp=ai;for(j=i+1;j<n;j+)if(temp>aj)ppp2+;k=aj;aj=temp;temp=k;ai=temp;cout<<"選擇排序耗時(shí)為： "<<ppp2/100000<<"毫秒"<<endl;elsefor(i=0;i<n-1;i+)temp=ai;s

22、trcpy(trtemp,sti);for(j=i+1;j<n;j+)if(temp>=aj)strcpy(trt,stj);strcpy(stj,trtemp);strcpy(trtemp,trt);k=aj;aj=temp;temp=k;strcpy(sti,trtemp);ai=temp;ai/=100000;ai/=100000;快速排序void quick(long int a,long int left,long int right)long int i=left,j=right,temp;temp=ai;if(j>i)while(j>i)while(aj&

23、gt;temp)&&(i<j)j-;if(i<j)ppp3+;ai=aj;i+;while(ai<temp)&&(i<j)i+;if(i<j)ppp3+;aj=ai;j-;ai=temp;quick(a,left,i-1);quick(a,i+1,right);void Quick(long int a)long int i=0,j=N-1;pubction(a);/cout<<"初始數(shù)組是：n"/print(a);quick(a,i,j);/cout<<"快速排序后數(shù)組是：n&

24、quot;/print(a);cout<<"快速排序耗時(shí)為： "<<ppp3/100000<<"毫秒"<<endl;堆排序void creatheap(long int a,long int i,long int n)long int j,temp;temp=ai;j=2*i+1;while(j<=n)if(j<=n)if(j+1<=n)if(aj<aj+1)j+;if(temp<aj)ppp4+;ai=aj;i=j;j=2*i+1;else j=n+1;ai=temp;voi

25、d heapsort(long int a)int temp,j;int n=N-1;pubction(a);/cout<<"初始數(shù)組為：n"/print(a);for(int i=n/2;i>=0;i-)creatheap(a,i,n);for(j=n;j>=1;j-)temp=a0;a0=aj;aj=temp;creatheap(a,0,j-1);/cout<<"堆排序后的數(shù)組是:n"/print(a);cout<<"堆排序耗時(shí)為： "<<ppp4/100000<&

26、lt;"毫秒"<<endl;二路歸并排序void merge(long int a,long int c,long int l,long int m,long int n)long int i=l,j=m,k=l;if(ai>aj)ck=aj;j+;elseck=ai;i+;k+;while(i<m)&&(j<n)while(ai<aj)&&(i<m)&&(j<n)ppp5+;ck=ai;k+;i+;while(ai>=aj)&&(i<m)&&

27、amp;(j<n)ppp5+;ck=aj;k+;j+;if(i>=m)while(j<n)ppp5+;ck=aj;k+;j+;else if(j>=n)while(i<m)ppp5+;ck=ai;k+;i+;for(long int p=l;p<n;p+)ap=cp;void mergesort(long int a)long int cN,d=1,i=0;/cout<<"初始數(shù)組為：n"pubction(a);/print(a);for(d;d<N-1;d*=2)i=0;while(i<N)if(i+d>=N-1)merge(a,c,i,N,N);e