算法分析与设计实验报告.doc

《算法分析与设计实验报告.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;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;j

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