欢迎来到天天文库
浏览记录
ID:59524614
大小:99.75 KB
页数:6页
时间:2020-11-07
《实验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(left6、的运行时间。特别是在数据基本有序的情况下,加入随机化过程应该能大大提高速度。计算算法运行的时间和程序运行的时间是不一样的,刚开始我把计算算法运行时间的函数start()的位置弄错了,自己不知道还是助教学长的提醒,才知道自己的错误,导致后面运行的时候得出来的时间有7,8秒了,是把我的输入的时间也算进去了,没有得到准确的算法运行时间。改变计算时间函数的位置后,算法运行的时间才正确了。实验得分助教签名附录:完整代码#include#include#include7、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;i8、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
6、的运行时间。特别是在数据基本有序的情况下,加入随机化过程应该能大大提高速度。计算算法运行的时间和程序运行的时间是不一样的,刚开始我把计算算法运行时间的函数start()的位置弄错了,自己不知道还是助教学长的提醒,才知道自己的错误,导致后面运行的时候得出来的时间有7,8秒了,是把我的输入的时间也算进去了,没有得到准确的算法运行时间。改变计算时间函数的位置后,算法运行的时间才正确了。实验得分助教签名附录:完整代码#include#include#include7、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;i8、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
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;i8、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
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
此文档下载收益归作者所有