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

《计算机算法设计与分析实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华北电力大学实验报告

2、

3、实验名称算法设计实验课程名称算法设计与分析

4、

5、专业班级：信安1301学生姓名：学号：成绩：指导教师：胡朝举实验日期：2015年11月实验一、归并排序(MergingSort)——分治策略一、 实验内容归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：（1）编写一个模板函数：templateMergeSort(T*a,intn);以及相应的一系列函数，采用分治策略，对任意具有:booloperator<(constT&x,constT&y)

6、;比较运算符的类型进行排序。（2）与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题,给出所用的时间比较。归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。二、 主要思想假设初始序列含有n个记录，则可看成n个有序的子序列，每个字序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，...，如此重复，直到一个长度为n的有序序列为止。例已知

7、待排序记录的关键字序列为{49,38,65,97,76,13,27}，给出2-路归并排序法进行排序的过程2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。相邻两个有序子序列的归并设两个有序表存放在同一数组中相邻的位置上：R[low..mid]和R[mid+1..high]，每次分被从两个表中取出一个记录进行关键字的比较，将较小者放入T[low..high]中，重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。三、 实验结果四、算法分析1)时间复杂

8、度当有n个记录时，需进行[log2n]趟归并排序,每一趟归并,其关键字比较次数不超过n,元素移动次数都是n,因此,归并排序的时间复杂度为O(nlog2n)。2)空间复杂度用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为O(n);五、 实验代码#include#include#include#include#includeusingnamespacestd;template

9、assType>voidMergSort(Typea[],intn){Type*b=newType[n];ints=1;while(svoidMergPass(Typex[],Typey[],ints,intn){inti=0;while(i<=n-2*s){Merg(x,y,i,i+s-1,i+2*s-1);i=i+2*s;}if(i+s

10、i+s-1,n-1);else{//如果剩下的不够i+s，则把剩下的放入y中for(intj=i;j<=n-1;j++){y[j]=x[j];}}}templatevoidMerg(Typec[],Typed[],intl,intm,intr){inti=l,j=m+1,k=l;while((i<=m)&&(j<=r)){if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];}if(i>m)for(intq=j;q<=r;q++)d[k++]=c[

11、q];elsefor(intq=i;q<=m;q++)d[k++]=c[q];}floatrandf(floatbase,floatup){return(rand()%(int)((up-base)*RAND_MAX))/(float)RAND_MAX;//产生随机数}voidprintArray(float*a,intN){for(inti=0;i<=N;i++){cout<

12、en];float*arrays=newfloat[ArrayLen];floatmn,ene;printf("数组已建立：");srand((unsigned)time(NULL));//设置随机数的seedfor(inti=0;i