算法设计实验一归并排序(分治)和插入排序的比较分析.pdf
《算法设计实验一归并排序(分治)和插入排序的比较分析.pdf》由会员分享,可在线阅读,更多相关《算法设计实验一归并排序(分治)和插入排序的比较分析.pdf(8页珍藏版)》请在三一文库上搜索。
1、沈阳化工大学实验报告 课程名称算法设计与分析 项目名称归并排序 ( 分治) 和插入排序的比较 学院应用技术学院 专业计中职 1401 指导教师张雪 报 告 人张庭浩学号 1422030125 实验时间 2016.11.05 提交时间 2016.11.05 一、实验目的 1.理解和掌握分治算法的相关内容。 2.具体完成插入排序和归并排序性能的比较。 二、实验内容 编写一个真随机函数,随机产生大量数字。在产生相同的一组大量随机数字后,分别用 归并排序和插入排序两种算法进行排序,并通过时间函数分别计算出运行的时间。 三、伪代码 1.归并排序 /*数组 a是原始数组,数组b是目标数组 */ 归并排序(
2、数组a,数组b ) 分割与归并(数组a,0, a.length,数组b) /*通过递归把要排序的子序列分的足够小*/ 分割与归并(数组a, 起始位置 ,结束位置 ,数组b) if( 结束位置- 起始位置 结束位置或 ai0 #include #include #define N 30000 typedef int RecType;/ 要排序元素类型 void Merge(RecType *R,int low,int m,int high) / 将 两 个 有 序 的 子 文 件Rlowm) 和Rm+1high 归 并 成 一 个 有 序 的 子 文 件 Rlowhigh int i=low,j
3、=m+1,p=0; /置初始值 RecType *R1; /R1 是局部向量 R1=(RecType *)malloc(high-low+1)*sizeof(RecType); if(!R1) return; /申请空间失败 while(i=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 日内。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 实验 归并 排序 分治 插入 比较 分析
链接地址:https://www.31doc.com/p-4746796.html