实验2-分治法实现归并排序.docx

《实验2-分治法实现归并排序.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计实验报告第2次实验姓名学号班级时间10.17上午地点工训楼309实验名称利用分治法实现归并排序算法实验目的通过上机实验，要求掌握分治法解决问题，以及二路归并算法的实现。实验原理使用分治法和二路归并算法，根据不同的随机数规模和数量，能准确的输出通过二路归并排序后的数组，并计算出程序运行所需要的时间。实验步骤①先输入随机数组的长度和规模；②产生一个随机数组；③计时开始，调用排序函数；④输出排序后的数组，输出算法话费的时间。关键代码template//将b[0]至b[righ

2、t-left+1]拷贝到a[left]至a[right]voidCopy(Ta[],Tb[],intleft,intright){intsize=right-left+1;for(inti=0;ivoidMerge(Ta[],Tb[],intleft,inti,intright){inta1cout=left,//指向第一个数组开

3、头a1end=i,//指向第一个数组结尾a2cout=i+1,//指向第二个数组开头a2end=right,//指向第二个数组结尾bcout=0;//指向b中的元素for(intj=0;ja1end){b[bcout++]=a[a2cout++];continue;}//如果第一个数组结束，拷贝第二个数组的元素到bif(a2cout>a2end){b[bcout++]=a[a1cout++];contin

4、ue;}//如果第二个数组结束，拷贝第一个数组的元素到bif(a[a1cout]voidMergeSort(Ta[],intleft,intright){T*b=newint[right-left+1

5、];if(left

6、的运行时间。特别是在数据基本有序的情况下，加入随机化过程应该能大大提高速度。计算算法运行的时间和程序运行的时间是不一样的，刚开始我把计算算法运行时间的函数start（）的位置弄错了，自己不知道还是助教学长的提醒，才知道自己的错误，导致后面运行的时候得出来的时间有7,8秒了，是把我的输入的时间也算进去了，没有得到准确的算法运行时间。改变计算时间函数的位置后，算法运行的时间才正确了。实验得分助教签名附录：完整代码#include#include#include

7、anip>#includeusingnamespacestd;template//将b[0]至b[right-left+1]拷贝到a[left]至a[right]voidCopy(Ta[],Tb[],intleft,intright){intsize=right-left+1;for(inti=0;i

8、sT>voidMerge(Ta[],Tb[],intleft,inti,intright){inta1cout=left,//指向第一个数组开头a1end=i,//指向第一个数组结尾a2cout=i+1,//指向第二个数组开头a2end=right,//指向第二个数组结尾bcout=0;//指向b中的元素for(intj=0;ja1end){b[bcout++]=a[a2c