计算机算法设计和分析实验报告

1、华北电力大学实验报告|实验名称算法设计实验课程名称算法设计与分析|专业班级：信安1301专业班级：信安1301学 号：指导教师：胡朝举学生：成 绩：实验日期：2015年11月实验一、归并排序(实验一、归并排序(Merging Sort)分治策略一、实验容归并排序是一个非常优秀的排序方法，也是典型的分治策略的典型应用。实验要求：编写一个模板函数：template MergeSort(T *a, int n);以及相应的一系列函数，采用分治策略，对任意具有：bool operator(c onst T& x,c onst T&y);比较运算符的类型进行排序。 与STL库中的函数std:sort(.

2、)进行运行时间上的比较，给出比较结果，如：动态生成 100万个随机生成的附点数序列的排序列问题，给出所用的时间比较。归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。二、主要思想假设初始序列含有 n个记录，则可看成 n个有序的子序列，每个字序列的长度为 1，然后两两归并， 得到n/2个长度为2或1的有序子序列；再两两归并， ，如此重复，直到一个长度为 n的有序序列 为止。例已知待排序记录的关键字序列为49,38,65,97,76,13,27，给出2-路归并排序法进行排序的过程初始关键字49 t138 |651 ,97 |176113|

3、27一趟片并之后3849|L,16597)113?6|2 I!7二越归并之后卩84965L.97B27|狗三趟归并之后1327384965761丁7|厶路归并排序过程2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。相邻两个有序子序列的归并设两个有序表存放在同一数组中相邻的位置上：Rlow.mid禾口 Rmid+1.high，每次分被从两个表中取出一个记录进行关键字的比较，将较小者放入Tlow.high中，重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。三、实验结果四、算法分析时间复杂度当有n个记录时，需进行log2n趟归并排序，

4、每一趟归并，其关键字比较次数不超过n, 元素移动次数都是n,因此，归并排序的时间复杂度为O(nlog2n)。空间复杂度用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复 杂度为0(n);五、实验代码#in clude#i nclude#in clude#i nclude#i ncludeusing n amespace std;templatevclass Typevoid MergSort(Type a, int n)Type *b = new Type n;int s = 1;while (s void MergPass(Type x, Type y, int s,

5、 int n)int i = 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 (i nt j = i; j void Merg(Type c, Type d, int l, i nt m, int r)int i = l, j = m + 1, k = l;while (i = m) & (j = r)if (ci m)for (int q =

6、j; q = r; q+)dk+ = cq;elsefor (int q = i; q = m; q+)dk+ = cq;float ran df(float base, float up)return (ran d() % (in t)(up - base) * RAND_MAX) / (float)RAND_MAX ; /产生随机数void prin tArray(float *a,i nt N)for(i nt i=0;i=N;i+)coutaie ndl;void mai n()int ArrayLe n = 5;float *array = new floatArrayLe n;fl

7、oat *arrays = new floatArrayLe n;float mn, ene;printf(数组已建立：n);srand(unsigned)time(NULL); /设置随机数的 seedfor (int i = 0; i fflag;switch (fflag)case 0:break;case 1:MergSort(array, ArrayLe n);prin tArray(array, ArrayLe n); break;prin tf(=n);prin tf(n);clock_t s = 0, e = 0;s = clock();MergSort(array, ArrayLe n);e = clock();cout MergSort 运行了： (e - s) ms endl;clock_t start1 = 0, end1 = 0;start1 = clock();std:sort(&arrays0, & arraysArrayLe n);end1 = clock();cout std:sort 运行了： (end1 - start1) ms endl; int flag = 1;while (flag != 0)coutvv输入