欢迎来到天天文库
浏览记录
ID:48415242
大小:558.50 KB
页数:15页
时间:2020-01-24
《算法分析与设计实验报告.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、word格式算法设计与分析学院:计算机科学与技术学号:129074106姓名:张淼淼20141114....word格式1、当问题规模时,快速排序和插入排序各需多少时间?写清机器配置,列出五种规模下各自需要的时间。按照下列表格提交:快速排序所需时间(ms)插入排序所需时间(ms)两者相差多少N=1000.006000.019000-0.013000N=10000.0740000.724000-0.650000N=100000.03200064.657000-64.625000N=10000013.30000050.900000-37.6000
2、00N=100000053.500000117.700000-64.200000机器配置:Window732位Cpu:Inter(R)Core(TM)i3-2120cpu@3.30GHzAMDRadeonHD6450Graphics....word格式程序:#include#include#include#includeinta[1000000];....word格式intb[1000000];voidQuickSort(intlow,inthigh){longi
3、,j;intx;i=low;j=high;x=a[i];while(i=x&&i(j+1))QuickSort(j+1,high);}voidBinaryInsertSort(intlength){intlow,high,mid;inti,j,m;//m为保存待插入的元素for(i=1;i4、[i];low=0;high=i-1;//设置初始区while(low<=high){mid=(low+high)/2;if(m>=b[mid])low=mid+1;elsehigh=mid-1;}for(j=i-1;j>=high+1;j--)//high为插入位置b[j+1]=b[j];//后移元素,留出插入的空位b[high+1]=m;//将元素插入正确的位置}....word格式}voidmain(){time_tstart,finish;//time_t相当于longdoublebetween_time1,between_time25、,between_time;//1表示快速排序所需时间,2表示插入排序所需时间,between_time表示两种排序之间的差值struct_timebtimebuffer1,timebuffer2;intstartm,finishm;doubletotal1=0,total2=0;//1表示规模为N时,快速排序所需的累计时间,2表示规模为N是,插入排序所需的累计时间intN,i,j;//N表示问题规模printf("请输入问题的规模:");scanf("%d",&N);//对一堆数据进行排序,排序1000次,求其排序的平均时间for(i=6、0;i<1000;i++){srand((unsigned)time(NULL));//对每次的排序进行设置随机种子(即编号)for(j=0;j7、//}_ftime(&timebuffer1);finishm=timebuffer1.millitm;finish=timebuffer1.time;between_time1=difftime(finish,start);//找出时间差between_time1=1000*between_time1+finishm-startm;total1=total1+between_time1;//插入排序....word格式_ftime(&timebuffer2);startm=timebuffer2.millitm;start=timebuff8、er2.time;BinaryInsertSort(N);//printf("插入排序之后的数据为:");//for(i=0;i
4、[i];low=0;high=i-1;//设置初始区while(low<=high){mid=(low+high)/2;if(m>=b[mid])low=mid+1;elsehigh=mid-1;}for(j=i-1;j>=high+1;j--)//high为插入位置b[j+1]=b[j];//后移元素,留出插入的空位b[high+1]=m;//将元素插入正确的位置}....word格式}voidmain(){time_tstart,finish;//time_t相当于longdoublebetween_time1,between_time2
5、,between_time;//1表示快速排序所需时间,2表示插入排序所需时间,between_time表示两种排序之间的差值struct_timebtimebuffer1,timebuffer2;intstartm,finishm;doubletotal1=0,total2=0;//1表示规模为N时,快速排序所需的累计时间,2表示规模为N是,插入排序所需的累计时间intN,i,j;//N表示问题规模printf("请输入问题的规模:");scanf("%d",&N);//对一堆数据进行排序,排序1000次,求其排序的平均时间for(i=
6、0;i<1000;i++){srand((unsigned)time(NULL));//对每次的排序进行设置随机种子(即编号)for(j=0;j7、//}_ftime(&timebuffer1);finishm=timebuffer1.millitm;finish=timebuffer1.time;between_time1=difftime(finish,start);//找出时间差between_time1=1000*between_time1+finishm-startm;total1=total1+between_time1;//插入排序....word格式_ftime(&timebuffer2);startm=timebuffer2.millitm;start=timebuff8、er2.time;BinaryInsertSort(N);//printf("插入排序之后的数据为:");//for(i=0;i
7、//}_ftime(&timebuffer1);finishm=timebuffer1.millitm;finish=timebuffer1.time;between_time1=difftime(finish,start);//找出时间差between_time1=1000*between_time1+finishm-startm;total1=total1+between_time1;//插入排序....word格式_ftime(&timebuffer2);startm=timebuffer2.millitm;start=timebuff
8、er2.time;BinaryInsertSort(N);//printf("插入排序之后的数据为:");//for(i=0;i
此文档下载收益归作者所有