归并排序_归并排序java_归并排序复杂度_crcr的专栏

你是否正在寻找关于归并排序的内容？让我把最完美的东西奉献给你：

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]

i=low；j=m+1；k=low；//初始化
if(R[i].key<=R[j].key)
MR[k++]=R[i++]；
else
R[k++]=R[j++]；
MR[k++]=R[i++]；
//将R[low..m]中剩余的复制到MR中
MR[k++]=R[j++]；
//将R[m+1..high]中剩余的复制到MR中
}
}

Merge(R,MR,i,i+len-1,i+2*len-1)；
Merge(R,MR,i,i+len-1,n)；
for(j=i；j<=n；j++)
MR[j]=R[j]；
int len=1；
MergePass(R,MR,len,n)；
MergePass(MR,R,len,n)；
}
}
二路归并排序的过程需要进行「log2n「趟。每一趟归并排序的操作，就是将两个有序子文件进行归并，而每一对有序子文件归并时，记录的比较次数均小于等于记录的移动次数，记录移动的次数均等于文件中记录的个数n，即每一趟归并的时间复杂度为O(n)，。因此，二路归并排序的时间复杂度为O(nlog2n)。
二路归并排序是稳定的，因为在每两个有序子文件归并时，若分别在两个有序子文件中出现有相同关键字的记录Merge算法能够使前一个子文件中同一关键字的记录先复制，后一子文件中同一关键字的记录被后复制，从而确保它们的相对次序不会改变。

以上就是关于归并排序的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-7161-1.html