下载此文档

算法设计实验一归并排序(分治)和插入排序的比较.doc


文档分类:IT计算机 | 页数:约8页 举报非法文档有奖
1/8
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/8 下载此文档
文档列表 文档介绍
沈阳化工大学实验报告
课程名称算法设计与分析
项目名称归并排序(分治)和插入排序的比较
学院应用技术学院
专业计中职1401
指导教师张雪
报告人张庭浩学号 1422030125
实验时间
提交时间
实验目的


实验内容
编写一个真随机函数,随机产生大量数字。在产生相同的一组大量随机数字后,分别用归并排序和插入排序两种算法进行排序,并通过时间函数分别计算出运行的时间。
伪代码

/*数组a[]是原始数组,数组b[]是目标数组*/
归并排序(数组 a[],数组 b[]){
`分割与归并(数组 a[],0, ,数组 b[])
}
/*通过递归把要排序的子序列分的足够小*/
分割与归并(数组 a[],起始位置,结束位置,数组 b[]){
if(结束位置- 起始位置< 2)
返回
中间位置= (起始位置+结束位置)/2
分割与归并(数组 a[],起始位置,中间位置,数组 b[])
分割与归并(数组 a[],中间位置,结束位置,数组 b[])
归并(数组 a[],起始位置,中间位置,结束位置,数组 b[])
拷贝(数组 a[],起始位置,结束位置,数组 b[])
}
归并(数组 a[],起始位置,中间位置,结束位置,数组 b[]){
i0 = 起始位置,i1 = 中间位置
for j = 起始位置到结束位置
if(i0 < 中间位置且(i1 > 结束位置或 a[i0] <= a[i1]){
//当i0没有超过中间位置时,有两种情况要将a[i0]复制到b[j]上:
//,只要把剩下的复制过来就好;
//[i0]比a[i1]小
b[j]=a[i0]
i0++
} else {
b[j]=a[i1]
i1++
}
}
/*将已经排好序的数组b复制回数组a的相应位置*/
拷贝(数组 a[],起始位置,结束位置,数组 b[]){
for k = 起始位置到结束位置
a[k] = b[k]
}
插入排序
理论分析

Divide的步骤为m=(p+q)/2,因此为O(1),Combine步骤为merge()函数,Conquer步骤为分解为2个子问题,子问题大小为n/2,因此:归并排序的递归式:T(n)=2T(n/2)+O(n)
而求解递归式的三种方法有:
(1)替换法:主要用于验证递归式的复杂度。
(2)递归树:能够大致估算递归式的复杂度,估算完后可以用替换法验证。
(3)主定理:用于解一些常见的递归式。
最坏情况运行时间:O(nlgn)
最佳运行时间:O(nlgn)
插入排序(非递归)
在最坏情况下,数组完全逆序,插入第2个元素时要考察前1个元素,插入第3个元素时,要考虑前2个元素,……,插入第N个元素,要考虑前 N - 1 个元素。因此,最坏情况下的比较次数是 1 + 2 + 3 + ... + (N - 1),等差数列求和,结果为 N^2 / 2,所以最坏情况下的复杂度为 O(N^2)。

算法设计实验一归并排序(分治)和插入排序的比较 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数8
  • 收藏数0 收藏
  • 顶次数0
  • 上传人分享精品
  • 文件大小333 KB
  • 时间2017-07-24