快速排序与合并排序的分析与比较

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 伪代码描述(参考书本)排序函数:递归实现排序void qSort(int p,int r) if(p<r)qSort(p,q-1); /对左半段排序qSort(q+1,r);划分函数:确定基准元素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的元素放到左边区域while(a-j>ap); /大于ap的元素放到右边区域if(i>=j)break; /循环至i>=j时结束else int temp=ai; /满足条件就交换数据ai=aj;aj=temp;ap=aj; /while循环结束时满足ap:q-1中元素不大于aq+1:r中元素 aj=x;return j; /算法结束时返回划分点j,再由qSort递归/对右半段排序 int q=partition(p,

3、r); /确定基准元素对数组的划分1.3 复杂度分析对于输入序列ap:r,算法partition的计算时间为O(r-p-1),而快速排序的运行时间与划分是否对称有关.最环的情况是两个区域分别包含n-1和1个元素的情况,此时T(n)=O(n),而最好情况下每次划分所取的基准恰好为中值,此时partition的计算时间T(n)2在n大于1时满足T(n)=2T(n/2)+O(n),解为T(n)=O(nlogn).因此快速排序算法在平均情况下的时间复杂度也是O(nlogn).1.4 实验源代码#include <cstdlib>#include <iostream>#inclu

4、de <time.h>using namespace std;int partition(int *a,int p,int r) /划分函数确定基准元素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) /排序函数,递归实现排

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<<" 数字大小上限: "cin>>INPUT;cout<<endl<<" 数列元素个数: "cin>>NUM;int *k=new intNUM;cout<<endl<<" 随机数列生成: &qu

6、ot;<<endl;for (i=0;i<NUM;i+)*(k+i)=rand()%(INPUT-1);cout<<*(k+i)<<"t"start=clock(); /时间计数qSort(k,0,NUM-1);cout<<" 排序后数列: "<<endl;for (i=0;i<NUM;i+)cout<<*(k+i)<<"t" /执行算法输出后结束计时 finish=clock();cout<<endl<<"

7、; 用时为:"<<(double)(finish-start)/CLK_TCK<<"秒."<<endl; system("PAUSE");return EXIT_SUCCESS;1.5 实验结果实验截图所示:2 合并排序2.1 算法概述合并排序也采用了分治的策略,将带排序的集合一分为二,直至待排序的集合只剩下一个元素为止.然后不断合并2个排好序的数据段,直至排好整个序列.另外,以此延伸的自然合并排序法则是先用一次线性扫描找出所有已排好序的字数组段,然后将相邻的字数组段两两合并,构成更大的已排好序的子数组段,直

8、至整个序列排好.2.2 伪代码描述合并函数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中数据开始比较 if(ci<=cj)dk+=ci+; /小的排在dk数列的前边 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;合并函数2:合并相邻大小为s的子数组void mergePass(int *x,int *y,int s,int n) /n为数组总长度 int i=0;while(i<=n-2*s) /数组够长的情况下,合并2个大小为s的相邻数组 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+) /排序后复制到yyj=xj;合并函数3:合并排序算法void mergeSort

10、(int *a,int n)int *b=new int n; /动态分配一个一样大空间的b数组int s=1; /从大小为1开始合并while(s<n)mergePass(a,b,s,n);s+=s; /合并大小为s的相邻数组放在b中 mergePass(b,a,s,n); /合并到数组as+=s;2.3 复杂度分析对于n个元素的数组,一趟合并排序的过程如右图所示,一趟下来相邻长度为s的有序数组归并进行了|n2s|次,整个归并排序需进行|logn|趟.因此其时间复杂度可以算出为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<<" 数字大小上限: "cin>>INPUT; cout<<endl<<" 数列元素个数: "cin>>NUM; int *k=new intNUM; cout<<endl<<" 随机数列生成: "<<endl; for (i=0;i<NUM;i+)*(k+i)=rand()%(INPUT-1); cout<<*(k+i)<<"t"start=cloc

14、k(); mergeSort(k,NUM);cout<<" 排序后数列: "<<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 实验结

15、果实验截图所示:3 结果比较为了方便比较,我将两个排序算法合并到一个程序中,让他们使用同一组随机生成的数组排序.同时考虑到数列元素个数很多时,大量的输出十分影响程序执行的时间,因此在原程序上做了一些修改,取消了数列的输出,而只在屏幕上显示两种排序后所用的时间. .for (i=0;i<NUM;i+) *(k+i)=rand()%(INPUT-1);*(k1+i)=*(k+i); cout<<endl<<" 随机数列生成!"<<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