快速排序和归并排序.docx
- 文档编号:12970049
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:13
- 大小:168.75KB
快速排序和归并排序.docx
《快速排序和归并排序.docx》由会员分享,可在线阅读,更多相关《快速排序和归并排序.docx(13页珍藏版)》请在冰点文库上搜索。
快速排序和归并排序
实验课程:
算法分析与设计
实验名称:
归并分类与快速分类平均时间之比较(验证型实验)
实验目标:
(1)通过实验比较归并分类与快速分类算法在平均情况下哪一个更快。
(2)加深对时间复杂度概念的理解。
实验任务:
(1)用C/C++语言编程实现归并分类算法6.3和快速分类算法6.6。
对于快速分类,SPLIT中的划分元素采用三者A(low),A(high),A((low+high)/2)中其值居中者。
(2)随机产生20组数据(比如n=5000i,1≤i≤20)。
数据均属于范围(0,105)内的整数。
对于同一组数据,运行快速分类和归并分类算法,并记录各自的运行时间(以毫秒为单位)。
(3)根据实验数据及其结果来比较快速分类和归并分类算法的平均时间,并得出结论。
实验设备及环境:
PC;C/C++等编程语言。
实验主要步骤:
(1)明确实验目标和具体任务;
(2)理解实验所涉及的两个分类算法;
(3)编写程序实现两个分类算法;
(4)设计实验数据并运行程序、记录运行的结果;
(5)根据实验数据及其结果得出结论;
实验数据及运行结果、实验结果分析及结论:
一、实验数据
1、在窗口中输入10,即产生10组数组,并选择手动输入数据,因为手动输入数据数组中数据量太小,运行时间都是0毫秒。
(1)23445563436562356763432344
(2)22345565754678673456845786879845
(3)4885432659845232
(4)5687123565
(5)568887546532555
(6)9865321220478
(7)5658754565872365485421
(8)595454215484576592660
(9)595421874512356588877451
(10)58487123591577
2、在窗口中输入20,即将随机产生20组数据,每组有5000~100000个元素,元素均属于范围(0,105)内的整数。
输入“N”产生随机数据,程序附带显示数组数据功能,但是因为数据量过大,在此处不显示。
二、运行结果
1、手动输入:
2、随机输入
三、实验结果分析及结论
在20组随机数据中,发现有时候快速排序快,有时候是归并排序快,两者之间的运行时间存在一些波动,但是从总的统计结果中可以发现,快速排序的平均运行时间明显比归并排序花费得少,故快速排序速度比归并排序快。
附录:
实验代码
#include
#include
#include
usingnamespacestd;
voidmerge(intA[],intlow,intmid,inthigh);
voidmergesort(intA[],intlow,inthigh);
voidsplit(intA[],intlow,inthigh,int&w);
voidquicksort(intA[],intlow,inthigh);
voidshowsort(intA[],intlow,inthigh);
inta[100001];//进行排序的数组
intb[100001];//辅助存储的数组
intB[100001];//用于归并排序中辅助存储的数组
intmain()
{
intt1,t2,t;
inti,n;
cout<<"********************************"< cout<<"归并分类与快速分类平均时间之比较"< cout<<"********************************"< doublemergetime=0; doublequicktime=0; intnum; cout<<"请输入你要进行排序的数组个数: "< cin>>num; cout<<"是否手动输入? (Y/N)"; charR; cin>>R; if(R=='Y'||R=='y') { for(intd=0;d { cout<<"第"< "; cin>>n; for(intz=1;z<=n;z++) {cin>>a[z]; b[z]=a[z];} t1=clock(); mergesort(b,1,n); t2=clock(); t=t2-t1; mergetime=mergetime+t; showsort(b,1,n);//显示归并排序后的结果 cout<<"mergesort花费: "< t1=clock(); quicksort(a,1,n); t2=clock(); t=t2-t1; quicktime=quicktime+t; showsort(a,1,n);//显示快速排序后的结果 cout<<"quicksort花费: "< cout< } cout<<"**************************"< cout<<"mergesort平均时间: "< cout<<"quicksort平均时间: "< cout<<"**************************"< return0; } srand((unsigned)time(NULL)); for(intj=0;j { i=rand()%(int)(20)+1; n=5000*i; for(intk=0;k<=n;k++) { b[k]=a[k]=rand()%(int)(100001);//产生n个数,在0-100000范围内 } //cout<<"显示未排序的数组: "< //showsort(b,1,n);//显示未排序的数组 cout<<"第"< t1=clock(); mergesort(b,1,n); t2=clock(); t=t2-t1; mergetime=mergetime+t; //cout< //showsort(b,1,n);//显示归并排序后的结果 cout<<"mergesort花费: "< t1=clock(); quicksort(a,1,n); t2=clock(); t=t2-t1; quicktime=quicktime+t; //cout< //showsort(a,1,n);//显示快速排序后的结果 cout<<"quicksort花费: "< cout< } cout<<"**************************"< cout<<"mergesort平均时间: "< cout<<"quicksort平均时间: "< cout<<"**************************"< return0; } //合并A[low…mid]和A[mid+1…high]两个数组,并进行排序 voidmerge(intA[],intlow,intmid,inthigh) { intp,q,k; p=low; q=mid+1; k=low; while((p<=mid)&&(q<=high)) { if(A[p] { B[k]=A[p];p++; } else { B[k]=A[q];q++; } k++; } if(p==(mid+1)) { while((k<=high)&&(q<=high)) B[k++]=A[q++]; } else { while((k<=high)&&(p<=mid)) B[k++]=A[p++]; } for(inti=low;i<=high;i++) A[i]=B[i]; } //先将整个A数组分裂成若干个数组,然后再升序排列 voidmergesort(intA[],intlow,inthigh) { intmid; if(low { mid=(low+high)/2; mergesort(A,low,mid); mergesort(A,mid+1,high); merge(A,low,mid,high); } } //划分元素A[low]的新位置w voidsplit(intA[],intlow,inthigh,int&w) { inti=low; intx=A[low]; inttemp; for(intj=(low+1);j<=high;j++) { if(A[j]<=x) { i++; if(i! =j) { temp=A[i]; A[i]=A[j]; A[j]=temp; } } } temp=A[low]; A[low]=A[i]; A[i]=temp; w=i; } //按非降序排列的数组A中的元素 voidquicksort(intA[],intlow,inthigh) { intw; if(low { split(A,low,high,w); quicksort(A,low,w-1); quicksort(A,w+1,high); } } //显示归并排序后的结果 voidshowsort(intA[],intlow,inthigh) { for(inti=low;i<=high;i++) cout< cout< }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 快速 排序 归并