08计科(2)班王进 12号.docVIP

（上机实验报告） 姓名： 王 进 班级： 08 计科（2）班 学号： 080104021112 指导老师：秦明 完成时间：2011年 一．题目：归并排序 二．算法介绍 归并排序采用的是分治法。分治策略是将两个已排好序的集合归并成一个新的已排好序的集合。归并排序分两步走：1、划分元素。2、归并。这里是2路归并排序，即：假设初始序列含有n个记录，这些记录可划分成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并……如此重复，直至得到一个长度为n的有序序列为止。即为2路归并排序。 三．程序流程图 开始开始 开始 开始 int low, mid, high输入数据 int low, mid, high 输入数据] 退出Lowhigh?归并排序 meresort(int low ,int hing ) N 退出 Lowhigh? 归并排序 meresort(int low ,int hing ) mid=(low+high)/2mergsort(low,high)mergesort(mid+1,high)打印排序结果 mid=(low+high)/2 mergsort(low,high) mergesort(mid+1,high) 打印排序结果 K=1,J[1]=1 结束 结束 meresort(int low ,int hing ) meresort(int low ,int hing ) K=1,J[1]=1 打印排序结果K=1,J[1]=1 打印排序结果 K=1,J[1]=1 四．源程序及实验结果 #include stdio.h #define N 10 void merge(int a[],int b[],int low,int mid,int high) { int h,i,j,k; h=low,i=low,j=mid+1; while(h=midj=high) { if(a[h]=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(hmid) { for(k=j;k=high;k++) { b[i]=a[k]; i++; } } else { for(k=h;k=mid;k++) { b[i]=a[k]; i++; } } for(k=low;k=high;k++) { a[k]=b[k]; } for(int i=0;i10;i++) { printf(%d ,a[i]); } printf(\n\n); } void mergesort(int a[],int b[],int low,int high) { int mid; if(lowhigh) { mid=(low+high)/2; mergesort(a,b,low,mid); mergesort(a,b,mid+1,high); merge(a,b,low,mid,high); } } void main() { int a[N];//{310,285,179,652,351,423,861,254,450,520}; int b[N]; int i; printf(输入数组中待排序的数：\n); for(i=0;iN;i++) scanf(%d,a[i]); printf(\n); mergesort(a,b,0,9); } 结果截图 结果分析 实验采用二路归并的策越，先左子树后右子树，先将元素划分知道成最小的单元然后合并。第一次归并[310,285]归并成了[285,310]，第二次归并，[285,310,179]归并成了[179,285,310]，直到形成最终的结果，左边归并好了归并右边这样就有了两个各含5个元素的已分好类的子集合，最后的归并得到分好类的结果 时间复杂度：n个元素进行归并排序,共需 ?logn? ,每次所需比较关键字的次数不超过n, 共比较O(nlogn)次。每趟移动n个记录, 共移动O(nlogn)个记录。归并排序需要