实验二 分治法归并排序.docxVIP

教师签名： 课程算法导论学院专业(班级)姓名学号日期实验二分治法归并排序一、实验目的及要求（一）实验目的1、熟悉归并排序算法过程；2、验证归并排序算法复杂度。（二）实验要求1、合理添加计数器2、实现归并排序算法并验证复杂性3、掌握递归方法二、实验内容与步骤 1、设计归并排序算法2、在算法中添加计数器，累计比较次数（注意计数器要用全局变量）和递归调用次数3、完成算法分析4、用JAVA实现算法，分别运行5-10个记录的排序，分析比较次数和规模之间的关系5、判断运行结果是否与分析结果一致6、和实验一的结果比较复杂性差别（用图表）三、实验结果与分析 1、代码如下：（ n=8 ）import java.util.Scanner;public class GuiBingPaiXu static int com=0,use=0;/com表示比较次数，use表示递归调用次数public static void main(String args) int a = new int 8;Scanner scan = new Scanner (System.in);int r=0, t=a.length-1;int num;System.out.println(请输入8个整数：);/将输入的每个数记入数组for(int i=0;ia.length;i+)num = scan.nextInt();ai = num;/递归调用归并排序PaiXu(a,r,t);实验报告专用纸成绩：课程学院专业(班级)姓名学号日期 年 月 日/输出各个数据System.out.println(该8个整数从小到大是:);for(int i=0;ia.length;i+)System.out.print(ai+ );System.out.println(n比较次数:+com);System.out.println(递归调用次数:+use); /归并排序public static void PaiXu(int b, int r, int t) use+;/每递归调用一次，加一int s;int temp = new int b.length;if (r=t) return;elses=(r+t)/2;PaiXu(b,r,s);PaiXu(b,s+1,t);GuiBing(b,temp,r,s,t);for(int i=r;i=t;i+)bi=tempi; /归并 public static void GuiBing(int b,int temp, int r, int s,int t) int i=r,j=s+1,k=r; while (i=s & j=t) if (bi=bj) tempk+=bi+; else tempk+=bj+; com+;/每比较一次，加一 while(i=s) tempk+=bi+; while(j=t) tempk+=bj+; 教师签名： 实验报告专用纸成绩：课程学院专业(班级)姓名学号日期 年 月 日2、算法分析： 设待排序记录个数为n ， 该算法的基本语句是 归并算法的 循环体的 比较语句“if (bi1所以，归并排序算法 的时间复杂度为 O(nlog2n) 。 另外，归并排序算法递归调用次数为 2n-1 。3、结果如下：教师签名： 实验报告专用纸 n=5 n=8成绩：教师签名： 课程学院专业(班级)姓名学号日期 年 月 日由n = 5,6, ,10等数据的运行结果可知，随着问题规模n的增加，其时间复杂度（比较次数的执行）也增加，所以，该算法分析的判断正确。4、与 选择排序 的对比（时间复杂度）平均情况最好情况最坏情况选择排序O(n2)O(n2)O(n2)归并排序O(nlog2n)O(nlog2n)O(nlog2n) 从时间复杂度上看，归并排序的要小于选择排序， 并且实际上，在 问题规模相同 而 待排序记录顺序的整齐程度有所差异的