文档介绍：华北电力大学实验报告|| 实验名称算法设计实验课程名称算法设计与分析||专业班级: 信安 130 1学生姓名: 学号: 成绩: 指导教师: 胡朝举实验日期: 2015 年 11月华北电力大学实验报告第页共页实验一、归并排序(Merging Sort) ——分治策略一、实验内容归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求: ( 1)编写一个模板函数: template <typename T> MergeSort(T *a, int n); 以及相应的一系列函数,采用分治策略,对任意具有: bool operator<(const T&x,const T&y); 比较运算符的类型进行排序。(2)与 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<> #include<algorithm> #include<> #include<> #include<> using namespace std; template<class Type> void MergSort(Type a[], int n){ Type *b= new Type[n]; ints=1; while (s< n){ MergPass(a, b, s, n); s += s; MergPass(b, a, s, n); s += s;}} template<class Type> void MergPass(Type x[], Type y[], int s, 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 (int j= i;j <= n-1; j++){ y[j] = x[j]; }}} template<class Type> void Merg(Type c[], Type d[], int l, int m, int r){ 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 (int q= j;q <= r; q++) d[k++] = c[q]; else for (int q= i;q <= m; q++) d[k++] = c[q]; } float randf(float base, float up){ return (rand() % (int)((up - base) * RAND_MAX)) / (float)RAND_MAX ; //产生随机数} void printArray(float *a,int N){ for(int i=0;i<=