快速排序與合并排序的分析與比較

1、快速排序與合并排序的分析與比較1 快速排序1.1 算法概述快速排序算法基于分治策略,算法的基本思路是以ap為基準把ap:r劃分成3段ap:q-1,aq,aq+1:r,使得ap:q-1中任何元素小于等于aq,aq+1:r中任何元素大于等于aq.然后通過遞歸,分別對ap:q-1和aq+1:r進行排序,即形成排好序的ap:r隊列.1.2 偽代碼描述(參考書本)排序函數(shù):遞歸實現(xiàn)排序void qSort(int p,int r) if(p<r)qSort(p,q-1); /對左半段排序qSort(q+1,r);劃分函數(shù):確定基準元素ap對ap:r進行劃分int partition(int p,i

2、nt r) int i=p,j=r+1,temp,x=ap;while(true)while(a+i<ap&&i<r); /小于ap的元素放到左邊區(qū)域while(a-j>ap); /大于ap的元素放到右邊區(qū)域if(i>=j)break; /循環(huán)至i>=j時結(jié)束else int temp=ai; /滿足條件就交換數(shù)據(jù)ai=aj;aj=temp;ap=aj; /while循環(huán)結(jié)束時滿足ap:q-1中元素不大于aq+1:r中元素 aj=x;return j; /算法結(jié)束時返回劃分點j,再由qSort遞歸/對右半段排序 int q=partition(p,

3、r); /確定基準元素對數(shù)組的劃分1.3 復(fù)雜度分析對于輸入序列ap:r,算法partition的計算時間為O(r-p-1),而快速排序的運行時間與劃分是否對稱有關(guān).最環(huán)的情況是兩個區(qū)域分別包含n-1和1個元素的情況,此時T(n)=O(n),而最好情況下每次劃分所取的基準恰好為中值,此時partition的計算時間T(n)2在n大于1時滿足T(n)=2T(n/2)+O(n),解為T(n)=O(nlogn).因此快速排序算法在平均情況下的時間復(fù)雜度也是O(nlogn).1.4 實驗源代碼#include <cstdlib>#include <iostream>#inclu

4、de <time.h>using namespace std;int partition(int *a,int p,int r) /劃分函數(shù)確定基準元素ap對ap:r進行劃分 int i=p;int j=r+1;int temp;int x=ap;while(true)while(a+i<ap&&i<r);while(a-j>ap);if(i>=j)break;elseint temp=ai;ai=aj;aj=temp;ap=aj;aj=x;return j;void qSort(int *a,int p,int r) /排序函數(shù),遞歸實現(xiàn)排

5、序if(p<r)int q=partition(a,p,r);qSort(a,p,q-1);qSort(a,q+1,r);int main()clock_t start,finish;int INPUT,NUM,i,x;void randomize();cout<<" 數(shù)字大小上限: "cin>>INPUT;cout<<endl<<" 數(shù)列元素個數(shù): "cin>>NUM;int *k=new intNUM;cout<<endl<<" 隨機數(shù)列生成: &qu

6、ot;<<endl;for (i=0;i<NUM;i+)*(k+i)=rand()%(INPUT-1);cout<<*(k+i)<<"t"start=clock(); /時間計數(shù)qSort(k,0,NUM-1);cout<<" 排序后數(shù)列: "<<endl;for (i=0;i<NUM;i+)cout<<*(k+i)<<"t" /執(zhí)行算法輸出后結(jié)束計時 finish=clock();cout<<endl<<"

7、; 用時為:"<<(double)(finish-start)/CLK_TCK<<"秒."<<endl; system("PAUSE");return EXIT_SUCCESS;1.5 實驗結(jié)果實驗截圖所示:2 合并排序2.1 算法概述合并排序也采用了分治的策略,將帶排序的集合一分為二,直至待排序的集合只剩下一個元素為止.然后不斷合并2個排好序的數(shù)據(jù)段,直至排好整個序列.另外,以此延伸的自然合并排序法則是先用一次線性掃描找出所有已排好序的字數(shù)組段,然后將相鄰的字數(shù)組段兩兩合并,構(gòu)成更大的已排好序的子數(shù)組段,直

8、至整個序列排好.2.2 偽代碼描述合并函數(shù)1:合并cl:m和cm+l:r到dl:rvoid merge(int *c,int *d,int l,int m,int r) int i=l;int j=m+1;int k=l;while(i<=m)&&(j<=r) /cl:m和cm+l:r中數(shù)據(jù)開始比較 if(ci<=cj)dk+=ci+; /小的排在dk數(shù)列的前邊 elsedk+=cj+; /大的排在后邊if(i>m) /將cm+l:r中剩下的元素移入dkfor(int q=j;q<=r;q+)dk+=cq;else /將cl:m中剩下的元素移入dk

9、for(int q=i;q<=m;q+)dk+=cq;合并函數(shù)2:合并相鄰大小為s的子數(shù)組void mergePass(int *x,int *y,int s,int n) /n為數(shù)組總長度 int i=0;while(i<=n-2*s) /數(shù)組夠長的情況下,合并2個大小為s的相鄰數(shù)組 merge(x,y,i,i+s-1,i+2*s-1);i=i+2*s;if(i+s<n) /所剩元素少于2s的情況merge(x,y,i,i+s-1,n-1);elsefor(int j=i;j<n;j+) /排序后復(fù)制到y(tǒng)yj=xj;合并函數(shù)3:合并排序算法void mergeSort

10、(int *a,int n)int *b=new int n; /動態(tài)分配一個一樣大空間的b數(shù)組int s=1; /從大小為1開始合并while(s<n)mergePass(a,b,s,n);s+=s; /合并大小為s的相鄰數(shù)組放在b中 mergePass(b,a,s,n); /合并到數(shù)組as+=s;2.3 復(fù)雜度分析對于n個元素的數(shù)組,一趟合并排序的過程如右圖所示,一趟下來相鄰長度為s的有序數(shù)組歸并進行了|n2s|次,整個歸并排序需進行|logn|趟.因此其時間復(fù)雜度可以算出為O(nlogn).2.4 實驗源代碼#include <cstdlib>#include <

11、iostream>#include <time.h>using namespace std;void merge(int *c,int *d,int l,int m,int r)int i=l;int j=m+1;int k=l;while(i<=m)&&(j<=r)if(ci<=cj)dk+=ci+;elsedk+=cj+;if(i>m)for(int q=j;q<=r;q+)dk+=cq;elsefor(int q=i;q<=m;q+)dk+=cq;void mergePass(int *x,int *y,int s,i

12、nt n)int i=0;while(i<=n-2*s)merge(x,y,i,i+s-1,i+2*s-1);i=i+2*s;if(i+s<n)merge(x,y,i,i+s-1,n-1);elsefor(int j=i;j<n;j+)yj=xj;void mergeSort(int *a,int n)int *b=new int n;int s=1;while(s<n)mergePass(a,b,s,n);s+=s;mergePass(b,a,s,n);s+=s;int main()clock_t start,finish; int INPUT,NUM,i,x;voi

13、d randomize(); cout<<" 數(shù)字大小上限: "cin>>INPUT; cout<<endl<<" 數(shù)列元素個數(shù): "cin>>NUM; int *k=new intNUM; cout<<endl<<" 隨機數(shù)列生成: "<<endl; for (i=0;i<NUM;i+)*(k+i)=rand()%(INPUT-1); cout<<*(k+i)<<"t"start=cloc

14、k(); mergeSort(k,NUM);cout<<" 排序后數(shù)列: "<<endl; for (i=0;i<NUM;i+)cout<<*(k+i)<<"t"finish=clock();cout<<endl<<" 用時為:"<<(double)(finish-start)/CLK_TCK<<"秒."<<endl; system("PAUSE");return 0;2.5 實驗結(jié)

15、果實驗截圖所示:3 結(jié)果比較為了方便比較,我將兩個排序算法合并到一個程序中,讓他們使用同一組隨機生成的數(shù)組排序.同時考慮到數(shù)列元素個數(shù)很多時,大量的輸出十分影響程序執(zhí)行的時間,因此在原程序上做了一些修改,取消了數(shù)列的輸出,而只在屏幕上顯示兩種排序后所用的時間. .for (i=0;i<NUM;i+) *(k+i)=rand()%(INPUT-1);*(k1+i)=*(k+i); cout<<endl<<" 隨機數(shù)列生成!"<<endl;start=clock();mergeSort(k,NUM); /合并排序finish=clock();cout<<endl<<" 合并排序用時為:"<<(double)(finish-start)/CLK_TCK<<"秒."<<endl;start=clock();qSort(k1,0,NUM-1); /快速排序finish=clock();cout<<endl<<" 快速排序用時為:"<<(double)(finis