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

华北电力大学
实验报告
|
|

实验名称算法设计实验
课程名称算法设计与分析
|
|
专业班级：信安1301学生姓名：
学号：成绩：
指导教师：胡朝举实验日期：2015年11月

实验一、归并排序(MergingSort)——分治策略
实验内容
归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：
（1）编写一个模板函数：
template<typenameT>
MergeSort(T*a,intn);
以及相应的一系列函数，采用分治策略，对任意具有:
booloperator<(constT&x,constT&y);
比较运算符的类型进行排序。
与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题,给出所用的时间比较。
归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。
二、主要思想
假设初始序列含有n个记录，则可看成n个有序的子序列，每个字序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，...，如此重复，直到一个长度为n的有序序列为止。
例已知待排序记录的关键字序列为{49,38,65,97,76,13,27}，给出2-路归并排序法进行排序的过程

2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。相邻两个有序子序列的归并
设两个有序表存放在同一数组中相邻的位置上：R[low..mid]和R[mid+1..high]，每次分被从两个表中取出一个记录进行关键字的比较，将较小者放入T[low..high]中，重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。
实验结果
算法分析
1)时间复杂度当有n个记录时，需进行[log2n]趟归并排序,每一趟归并,其关键字比较次数不超过n,元素移动次数都是n,因此,归并排序的时间复杂度为O(nlog2n)。2)空间复杂度用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为O(n);
实验代码
#include<iostream.h>
#include<algorithm>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
usingnamespacestd;
template<classType>
voidMergSort(Typea[],intn){
Type*b=newType[n];
ints=1;
while(s<n){
MergPass(a,b,s,n);
s+=s;
MergPass(b,a,s,n);
s+=s;
}
}
template<classType>
voidMergPass(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<n)
Merg(x,y,i,i+s-1,n-1);
else{//如果剩下的不够i+s，则把剩下的放入y中
for(intj=i;j<=n-1;j++){
y[j]=x[j];
}
}
}
template<classType>
voidMerg(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++];
else
d[k++]=c[j++];

}
if(i>m)
for(intq=j;q<=r;q++)
d[k++]=c[q];
else
for(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<<a[i]<<endl;
}
}

voidmain(){
intArrayLen=5;
float*array=newfloat[ArrayLen];
float*arrays=newfloat[ArrayLen];
floatmn,ene;
pri