數(shù)據(jù)結構課程設計--排序算法比較

1、 數(shù)據(jù)結構與算法設計課程設計報告 題目： 排序算法比較 學生姓名： 汪洪 學 號： 201120181805 班 級： 1121822 指導教師： 周華清 2013年1月10日目錄需求分析··································&#

2、183;·····3總體設計········································4詳細設計··

3、3;·····································5類的設計············

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

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

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

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

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

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

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

11、···································21總結··············&#

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

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

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

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

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

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

18、插入排序。依次使N=N/2縮小間隔。最終作一次直接插入排序。實現(xiàn)部分對數(shù)組隨機賦值void pubction()srand(time(NULL);for(long int i=0;i<N;i+) ai=rand()%90000;輸出數(shù)組前30個元素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<<"直接插入排序耗時： "<<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<<"冒泡排序耗時為： "<<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<<"選擇排序耗時為： "<<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<<"快速排序耗時為： "<<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<<"堆排序耗時為： "<<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