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
相关推荐
MATLAB实现《算法设计与分析》中的插入排序、二分归并排序、归并排序实验,其中包括.m文件和实验报告,安徽大学本科课程。
试通过随机数据比较归并排序、基数排序各算法的关键字比较次数和关键字移动次数。 (1)待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有。关键字...
归并排序C语言实现
C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
根据算法导论实现的归并排序算法
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
归并排序,比较高效的排序算法之一。这是一个例子,一个关于归并排序的例子。
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
c语言实现归并排序,递归方式实现,含详细注释
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
实现归并排序的一个类
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
本人自己写的一些排序算法,这是系列1归并排序算法实现,