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

沈阳化工大学实验报告课程名称算法设计与分析项目名称归并排序(分治)。。实验内容编写一个真随机函数,随机产生大量数字。在产生相同的一组大量随机数字后,分别用归并排序和插入排序两种算法进行排序,并通过时间函数分别计算出运行的时间。/*数组a[]是原始数组,数组b[]是目标数组*/归并排序(数组a[],数组b[]){`分割与归并(数组a[],0,,数组b[])}/*通过递归把要排序的子序列分的足够小*/分割与归并(数组a[],起始位置,结束位置,数组b[]){if(结束位置-起始位置<2)返回中间位置=(起始位置+结束位置)/2分割与归并(数组a[],起始位置,中间位置,数组b[])分割与归并(数组a[],中间位置,结束位置,数组b[])归并(数组a[],起始位置,中间位置,结束位置,数组b[])拷贝(数组a[],起始位置,结束位置,数组b[])}归并(数组a[],起始位置,中间位置,结束位置,数组b[]){i0=起始位置,i1=中间位置forj=起始位置到结束位置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[]){fork=起始位置到结束位置a[k]=b[k]}=(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)。,接下来我们将进行实际算法的实现用实践来论证我们的理论。测试用例首先我们先测试一下程序的正确性。插入排序测试数据:49,38,65,97,76,13,27,49归并排序测试数据:49,38,65,97,76,13,27,100性能测试相同的三万个随机数进行排序证明了我们之前理论是正确的。通过实践,,。七、源代码#include<>#inc