实验二 分治法归并排序

《实验二 分治法归并排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除教师签名：课程算法导论学院专业(班级)姓名学号日期实验二分治法归并排序一、实验目的及要求（一）实验目的1、熟悉归并排序算法过程；2、验证归并排序算法复杂度。（二）实验要求1、合理添加计数器2、实现归并排序算法并验证复杂性3、掌握递归方法二、实验内容与步骤1、设计归并排序算法2、在算法中添加计数器，累计比较次数（注意计数器要用全局变量）和递归调用次数3、完成算法分析4、用JAVA实现算法，分别运行5-10个记录的排序，分析比较次数和规模之间的关系5、判断运行结果是否与分析结果一致6、和实验一的结果比较复杂性差别（用图表）三、实验结果与分析1、代码如

2、下：（n=8）importjava.util.Scanner;publicclassGuiBingPaiXu{staticintcom=0,use=0;//com表示比较次数，use表示递归调用次数publicstaticvoidmain(String[]args){int[]a=newint[8];Scannerscan=newScanner(System.in);intr=0,t=a.length-1;intnum;System.out.println("请输入8个整数：");//将输入的每个数记入数组for(inti=0;i

3、);a[i]=num;}//递归调用归并排序PaiXu(a,r,t);实验报告专用纸成绩：课程学院专业(班级)姓名学号日期年月日//输出各个数据System.out.println("该8个整数从小到大是:");for(inti=0;i

4、t[]temp=newint[b.length];if(r==t)return;else{s=(r+t)/2;PaiXu(b,r,s);PaiXu(b,s+1,t);GuiBing(b,temp,r,s,t);for(inti=r;i<=t;i++)b[i]=temp[i];}}//归并publicstaticvoidGuiBing(intb[],inttemp[],intr,ints,intt){inti=r,j=s+1,k=r;while(i<=s&&j<=t){if(b[i]<=b[j])temp[k++]=b[i++];elsetemp[k++]=b[j++];com++;//每比较一

5、次，加一}while(i<=s)temp[k++]=b[i++];while(j<=t)temp[k++]=b[j++];}}教师签名：实验报告专用纸成绩：课程学院专业(班级)姓名学号日期年月日2、算法分析：设待排序记录个数为n，该算法的基本语句是归并算法的循环体的比较语句“if(b[i]<=b[j])temp[k++]=b[i++];elsetemp[k++]=b[j++];”，其执行次数为：,即执行一趟归并算法的时间复杂度为。则归并排序算法存在以下推式：所以，归并排序算法的时间复杂度为。另外，归并排序算法递归调用次数为。3、结果如下：教师签名：实验报告专用纸n=5n=8成绩：教师签名：课程

6、学院专业(班级)姓名学号日期年月日由n=5,6,…,10等数据的运行结果可知，随着问题规模n的增加，其时间复杂度（比较次数的执行）也增加，所以，该算法分析的判断正确。4、与选择排序的对比（时间复杂度）平均情况最好情况最坏情况选择排序归并排序从时间复杂度上看，归并排序的要小于选择排序，并且实际上，在问题规模相同而待排序记录顺序的整齐程度有所差异的情况下，选择排序是不论待排序记录顺序的整齐程度如何，其时间复杂度都是固定的；归并排序是若待排序记录顺序越整齐，其时间复杂度越小，实验报告专用纸n=10成绩：【精品文档】第1页