《算法设计实验一归并排序(分治)和插入排序的比较》由会员分享，可在线阅读，更多相关《算法设计实验一归并排序(分治)和插入排序的比较（8页珍藏版）》请在金锄头文库上搜索。
1、沈阳化工大学实验报告课程名称 算法设计与分析 项目名称 归并排序(分治)和插入排序的比较 学 院 应用技术学院 专 业 计中职1401 指导教师 张雪 报 告 人 张庭浩 学号 1422030125 实验时间 2016.11.05 提交时间 2016.11.05 1、 实验目的 1.理解和掌握分治算法的相关内容。 2.具体完成插入排序和归并排序性能的比较。2、 实验内容 编写一个真随机函数，随机产生大量数字。在产生相同的一组大量随机数字后，分别用归并排序和插入排序两种算法进行排序，并通过时间函数分别计算出运行的时间。3、 伪代码1.归并排序/*数组a是原始数组，数组b是目标数组*/归并排序（数
2、组 a,数组 b） 分割与归并（数组 a,0, a.length,数组 b)/*通过递归把要排序的子序列分的足够小*/分割与归并（数组 a,起始位置,结束位置,数组 b) if(结束位置 - 起始位置 2) 返回 中间位置 = （起始位置+结束位置）/2 分割与归并（数组 a,起始位置,中间位置,数组 b) 分割与归并（数组 a,中间位置,结束位置,数组 b) 归并（数组 a,起始位置，中间位置，结束位置，数组 b) 拷贝（数组 a,起始位置，结束位置，数组 b)归并（数组 a,起始位置，中间位置，结束位置，数组 b) i0 = 起始位置，i1 = 中间位置 for j = 起始位置 到 结束
3、位置 if(i0 结束位置 或 ai0 = ai1) /当i0没有超过中间位置时，有两种情况要将ai0复制到bj上： /1.i1已经超过结束位置，只要把剩下的复制过来就好； /2.ai0比ai1小 bj=ai0 i0+ else bj=ai1 i1+ /*将已经排好序的数组b复制回数组a的相应位置*/拷贝（数组 a，起始位置，结束位置，数组 b） for k = 起始位置 到 结束位置 ak = bk2. 插入排序4、 理论分析1.归并算法 Divide的步骤为m=(p+q)/2，因此为O(1)，Combine步骤为merge()函数，Conquer步骤为分解为2个子问题，子问题大小为n/2，
4、因此：归并排序的递归式：T(n)=2T(n/2)+O(n)而求解递归式的三种方法有：(1)替换法：主要用于验证递归式的复杂度。(2)递归树：能够大致估算递归式的复杂度，估算完后可以用替换法验证。(3)主定理：用于解一些常见的递归式。 最坏情况运行时间：O(nlgn) 最佳运行时间：O(nlgn)2. 插入排序(非递归) 在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，插入第N个元素，要考虑前 N - 1 个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + . + (N - 1)，等差数列求和，结果为 N2 / 2，所以最坏情况下的复杂
5、度为 O(N2)。 3.结论 通过理论分析我们可以知道归并排序的效率高于插入排序，接下来我们将进行实际算法的实现用实践来论证我们的理论。5、 测试用例 首先我们先测试一下程序的正确性。1. 插入排序测试数据:49,38,65,97,76,13,27,492. 归并排序测试数据:49,38,65,97,76,13,27,1006、 性能测试 相同的三万个随机数进行排序证明了我们之前理论是正确的。通过实践，结果是归并运行0.01秒，直接插入排序运行时间0.56秒。七、源代码#include#include#include#define N 30000typedef int RecType;/要排序
6、元素类型 void Merge(RecType *R,int low,int m,int high) /将两个有序的子文件Rlow.m)和Rm+1.high归并成一个有序的子文件Rlow.high int i=low,j=m+1,p=0; /置初始值 RecType *R1; /R1是局部向量 R1=(RecType *)malloc(high-low+1)*sizeof(RecType); if(!R1) return; /申请空间失败 while(i=m&j=high) /两子文件非空时取其小者输出到R1p上 R1p+=(Ri=Rj)?Ri+:Rj+; while(i=m) /若第1个子文
7、件非空，则复制剩余记录到R1中 R1p+=Ri+; while(j=high) /若第2个子文件非空，则复制剩余记录到R1中 R1p+=Rj+; for(p=0,i=low;i=high;p+,i+) Ri=R1p; /归并完成后将结果复制回Rlow.high void MergeSort(RecType R,int low,int high) /用分治法对Rlow.high进行二路归并排序 int mid; if(lowhigh) /区间长度大于1 mid=(low+high)/2; /分解 MergeSort(R,low,mid); /递归地对Rlow.mid排序 MergeSort(R,
8、mid+1,high); /递归地对Rmid+1.high排序 Merge(R,low,mid,high); /组合，将两个有序区归并为一个有序区 void main() int low=0,high=N; /初始化low和high的值 clock_t start, end,s,e;int aN,i,num,flag,j,bN,lN,c,save,v;srand(unsigned)time(NULL); for(i=0;iN;+i) num=rand()%N+1; flag=1; for(j=0;ji;+j)/判断随机数是否重复 if(num=aj) flag=0; break; if(fla
9、g) /对随机数进行复制 ai=num; else -i;for(int k=0;kN;k+)bk=ak;lk=ak; start=clock(); MergeSort(b,low,high);end=clock();for(i=low;ihigh;i+) printf(%d ,bi); /输出测试 s=clock();for(c=1;c=0;v-) if(lvsave) break; lv+1=lv; /移动元素 if(v+1!=c) lv+1=save; /在合适位置放上之前保存的数 e=clock();for(c=0;cN;c+)printf(%8d,lc);printf(n); printf(归并排序时间:%0.2f秒n, (end-start)/1000.0); printf(直接插入排序时间:%0.2f秒n, (e-s)/1000.0);指导教师批阅意见：成绩评定： 指导教师签字：张雪 年 月 日备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
