归并排序

8.5 归并排序 　　 　　归并排序(MergeSort)的基本思想是：将待排序文件看成为n个长度为1的有序子文件，把这些子文件两两归并，使得到「n/2」个长度为2的有序子文件；然后再把这「n/2」个有序文件的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止，这种排序方法成为二路归并排序。例如，有初始关键字序列：72,18,53,36,48,31,36，其二路归并排序过程如下所示。 　　　　n=7 [72] [18] [53] [36] [48] [31] [36] 　　 一趟归并： [18 72] [36 53] [31 48] [36] 　　 二趟归并： [18 36 53 72] [31 36 48] 　　 三趟归并： [18 31 36 36 48 53 72] 　　二路归并排序中的核心操作是将数组中前后相邻的两个有序序列归并为一个有序序列，其算法如下： 　　void Merge(SeqList R,SeqList MR,int low,int m,int high) 　　{//对有序的R[low..m]和R[m+1..high] 　　　//归并为有序的MR[low..high] 　　　　i=low；j=m+1；k=low；//初始化 　　　　while(i<=m && j<=high) { 　　　　　if(R[i].key<=R[j].key) 　　　　　　 MR[k++]=R[i++]； 　　　　　else 　　　　　　 R[k++]=R[j++]； 　　 　 　while(i<=m) 　　　 　　 MR[k++]=R[i++]； 　　　　　　//将R[low..m]中剩余的复制到MR中 　　 　 　while(j<=high) 　　　 　　 MR[k++]=R[j++]； 　　　　　 //将R[m+1..high]中剩余的复制到MR中 　　　　 } 　　 } 　　一趟归并排序的基本思想是，在某趟归并中，设各子文件长度为len(最后一个子文件的长度可能会小于len)，则归并前R[1..n]中共有「n/len」个有序子文件。调用归并操作对子文件进行归并时，必须对子文件的个数可能是奇数、最后一个子文件的长度可能小于len这两种特殊情况进行处理：若子文件个数为奇数，则最后一个子文件无须和其它子文件归并；若文件个数为偶数，则要注意最后一对子文件中后一个子文件的区间上界为n。因此，具体的一趟归并排序算法如下： 　　void MergePass(SeqList R,SeqList MR,int len,int n) 　　{//对R[1..n]做一趟归并排序 　　　for(i=1；i+2*len-1<=n；i=i+2*len) 　　　　 Merge(R,MR,i,i+len-1,i+2*len-1)； 　　　if(i+len-1<n)//尚有两个子文件，其中最后一个长度<len 　　　　 Merge(R,MR,i,i+len-1,n)； 　　　else 　　　　 for(j=i；j<=n；j++) 　　　　　　MR[j]=R[j]； 　　　　 //文件个数为奇数，最后一个子文件复制到MR中 　　} 　　因此，整个归并排序算法如下： 　　void MergeSort(SeqList R,SeqList MR,int n) 　　{//对R[1..n]进行归并排序 　　　int len=1； 　　　while(len<n) { 　　　　 MergePass(R,MR,len,n)； 　　　　 len=len*2； 　　　　 MergePass(MR,R,len,n)； 　　 　} 　　 } 　　二路归并排序的过程需要进行「log2n「趟。每一趟归并排序的操作，就是将两个有序子文件进行归并，而每一对有序子文件归并时，记录的比较次数均小于等于记录的移动次数，记录移动的次数均等于文件中记录的个数n，即每一趟归并的时间复杂度为O(n)。因此，二路归并排序的时间复杂度为O(nlog2n)。 　　二路归并排序是稳定的，因为在每两个有序子文件归并时，若分别在两个有序子文件中出现有相同关键字的记录Merge算法能够使前一个子文件中同一关键字的记录先复制，后一子文件中同一关键字的记录被后复制，从而确保它们的相对次序不会改变。 http://media.openonline.com.cn/media_file/rm/zhongkeda2006/shujujiegou/link/content/chapt8_5_1.htm

[上一小节]