文档介绍：Forpersonaluseonlyinstudyandresearch;、实验概述:螆【实验目的】薄螁通过比较快速排序和归并排序法的时间复杂度,羆分析算法的好坏情况。袃通过该实验熟悉和掌握递归和分治策略的思想羂薀肅芄蚄荿荿蚅膂莂【实验原理】葿肆将一个难以解决的大问题分割成一个个规模较小的子问题,袄解决小的问题从而化解大的问题。膁蕿薇莁羀虿蚄肃【实验环境】蚈蝿Win7系统,VC++、实验内容:蚁【实验方案】艿羈编写程序采用分治法算法的思想,利用递归的算法结构,层层递进。羃将两种排序分别测试一定量的数据,并记录下所用的时间莃肈肈莄【实验过程】(实验步骤、记录、数据、分析)袁肁本实验利用系统函数计算算法运算时间,程序中采用宏定义K值来控制测试的数据量,依次改变K的大小,记录下显示的时间的变化和比较两种算法的运算的时间差异,分析数值的变化,从而来判定算法的优劣。膈螅【实验结论】(结果)薃随机取200000个数进行排序,计算时间如下:袀芈归并排序算法的计算时间:,程序函数计算时间结果如下:,快速排序算法时间:,;蒄从以上可以得出,在同样多的数据量情况下,快速排序明显要快于归并排序。莀薈膄【实验小结】(收获体会)袂算法的好坏决定程序的运行效率,在以后的编程中多分析算法的复杂度,选取合理的算法。腿薈三、指导教师评语及成绩:,字迹清楚,文字叙述流畅,(实验步骤详细,记录完整,数据合理,分析透彻):袁莆指导教师签名:蚅批阅日期:螁蚀附录1:源程序蒆//归并算法源程序肆//归并算法源程序蒃#include<>葿#include<>薆#defineK200000//改变k值,调整测试数据。蒇#include<>羁voidMerge(int*R,intlow,intm,inthigh)蒂{蚆//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]薄inti=low,j=m+1,p=0;//置初始值蚃int*R1;//R1是局部向量芁R1=(int*)malloc((high-low+1)*sizeof(int));螆if(!R1)羅{莄return;//申请空间失败罿}螆while(i<=m&&j<=high)//两子文件非空时取其小者输出到R1[p]上莅{袂R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];螈}袆while(i<=m)//若第1个子文件非空,则复制剩余记录到R1中螆{薄R1[p++]=R[i++];螁}羆while(j<=high)//若第2个子文件非空,则复制剩余记录到R1中袃{羂R1[p++]=R[j++];薀}肅for(p=0,i=low;i<=high;p++,i++)芄{蚄R[i]=R1[p];//归并完成后将结果复制回R[low..high]荿}荿}蚅膂voidMergeSort(intR[],intlow,inthigh)莂{//high--;葿//用分治法对R[low..high]进行二路归并排序肆intmid;袄if(low<high)膁{//区间长度大于1蕿mid=(low+high)/2;//分解薇MergeSort(R,low,mid);//递归地对R[low..mid]排序莁MergeSort(R,mid+1,high);//递归地对R[mid+1..high]排序羀Merge(R,low,mid,high);//组合,将两个有序区归并为一个有序区虿}蚄}肃voidmain()蚈{蝿 clock_tstart,finish;//计算系统时间肄doubletime;//计算时间值蒁inta[K];//这里对8个元素进行排序螁intlow=0,high=K;//初始化low和high的值衿 for(intj=0;j<K;j++)蒅 {芃 a[j]=rand();//%100000;蒀 }罿printf("Beforemergesort:");