实验报告专用纸
实验报告专用纸
成绩： 实验报告专用纸
课程
学院
专业
(班级)
姓名 学号 日期 年 月 日 2、算法分析： 设待排序记录个数为n ，
该算法的基本语句是 归并算法的 循环体的 比较语句 “if (b[i]<=b[j]) temp[k++]=b[i++]; else temp[k++]=b[j++]; ”，
其执行次数为： ,即执行一趟 归并算法 的时间复杂度为 。

则 归并排序算法存在以下推式：
所以，归并排序算法 的时间复杂度为 。

另外，归并排序算法递归调用次数为 。

3、结果如下：
n=5
n=8
成绩：
实验报告专用纸
课程学院
专业
(班级)
姓名学号日期年月日
由n = 5,6,…,10等数据的运行结果可知，
随着问题规模n的增加，其时间复杂度（比较次数的执行）也增加，
所以，该算法分析的判断正确。

4、与选择排序的对比（时间复杂度）
平均情况最好情况最坏情况选择排序
归并排序
从时间复杂度上看，归并排序的要小于选择排序，
并且实际上，
在问题规模相同而待排序记录顺序的整齐程度有所差异的情况下，
选择排序是不论待排序记录顺序的整齐程度如何，其时间复杂度都是固定的；
n=10
成绩：。