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

《算法分析报告与设计实验报告材料.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实用文档算法设计与分析学院：计算机科学与技术学号：129074106姓名：张淼淼实用文档201411141、当问题规模时，快速排序和插入排序各需多少时间？写清机器配置，列出五种规模下各自需要的时间。按照下列表格提交：快速排序所需时间(ms)插入排序所需时间（ms）两者相差多少N=1000.006000.019000-0.013000N=10000.0740000.724000-0.650000N=100000.03200064.657000-64.625000N=10000013.3000005

2、0.900000-37.600000N=100000053.500000117.700000-64.200000机器配置：Window732位Cpu：Inter(R)Core(TM)i3-2120cpu@3.30GHzAMDRadeonHD6450Graphics实用文档实用文档程序：#include#include#include#includeinta[1000000];intb[1000000];voidQui

3、ckSort(intlow,inthigh){longi,j;intx;i=low;实用文档j=high;x=a[i];while(i=x&&i(j+1))QuickSort(j+1,high);}voidBinaryInsertSort(intlength){intlow

4、,high,mid;inti,j,m;//m为保存待插入的元素for(i=1;i=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;//将元素插入正确的位置}}void

5、main(){time_tstart,finish;//time_t相当于longdoublebetween_time1,between_time2,between_time;实用文档//1表示快速排序所需时间，2表示插入排序所需时间，between_time表示两种排序之间的差值struct_timebtimebuffer1,timebuffer2;intstartm,finishm;doubletotal1=0,total2=0;//1表示规模为N时，快速排序所需的累计时间，2表示规模为N是

6、，插入排序所需的累计时间intN,i,j;//N表示问题规模printf("请输入问题的规模：");scanf("%d",&N);//对一堆数据进行排序，排序1000次,求其排序的平均时间for(i=0;i<1000;i++){srand((unsigned)time(NULL));//对每次的排序进行设置随机种子（即编号）for(j=0;j

7、ebuffer1.millitm;//实用文档start=timebuffer1.time;QuickSort(0,N-1);//printf("快速排序之后的数据为:");//for(i=0;i

8、between_time1=1000*between_time1+finishm-startm;total1=total1+between_time1;//插入排序_ftime(&timebuffer2);startm=timebuffer2.millitm;start=timebuffer2.time;BinaryInsertSort(N);//printf("插入排序之后的数据为:");//for(i=0;i