归并排序

概述

堆排序充分利用了完全二叉树的深度为floor(logn)+1的特性,效率非常高,但是堆的结构设计非常复杂,归并排序就是直接利用完全二叉树进行排序的简单的方法。
归并排序的原理是假设初始序列有n个记录,则可以看作是n个有序子序列,每个子序列的长度为1,然后两两归并,……,如此重复,直到得到一个长度为n的有序序列,这种排序方法称为2路归并排序

算法描述

设两个相邻的有序子序列为r[s]~r[m],r[m+1]~r[t],合并成一个有序序列暂存于r1[s]~r1[t]。为此设三个参数i,j,k分别指向两个待合并的子序列和最终的有序序列的起始位置处,即i = s,j = m+1,k = s;i,j向后遍历,取较小者,存于r1[k]位置处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int a[],int s,int m,int t){
int i = s,j = m+1,k = 0;
int r1[t-s+1];
while(i<=m && j <= t){ //取较小者暂存
if(a[i]<a[j])
r1[k++] = a[i++];
else
r1[k++] = a[j++];
}
while(i<=m)
r1[k++] = a[i++];
while(j<=t)
r1[k++] = a[j++];
for(int i = s;i<=t;i++) //将合并结果传回原数组
a[i] = r1[i-s];
}

在递归写法中,设2路归并排序的记录区间是r[s]~r[t],当待排区间的长度等于1时,递归结束:

1
2
3
4
5
6
7
8
9
void MergeSort1(int a[],int s,int t){
int m;
if(s == t)
return ;
m = (s+t)/2;
MergeSort1(a,s,m);
MergeSort1(a,m+1,t);
merge(a,s,m,t);
}


在该示例图中,递归的执行过程是从第一行一直到最后一行,而非递归的执行过程只是从中间划分完成的n个子序列开始到最后一行。

下面讨论非递归的实现
2路归并排序的非递归实现需要解决一些问题:

  1. 如何构造初始有序子序列?
  2. 怎样实现两两合并从而完成一趟排序?
  3. 排序何时结束?

对于问题1

如果有n个元素的序列,可以将其看成n个有序的子序列

问题2

在一趟归并排序中,有可能最后一个子序列的长度与前面的子序列长度h不同。现在是要将若干个相邻的长度为h的有序序列和最后一个长度可能小于h的有序序列两两合并,把结果放到r1[1]~r1[n]中。为此,设参数i指向待排序列的第一个记录,初始i=1,显然合并的步长应为2h,在归并的过程中有三种情况:
①:若i <= n-2h+1,则表示待合并的两个相邻子序列的长度均为h,执行一次合并。完成后i+2h,准备进行下一次合并。
②:若i < n-h+1,则表示仍有两个相邻有序子序列,一个长度为h,另一个小于h,执行一次合并,完成后退出一趟归并。
③:若i >= n-h+1,则表示只剩下一个有序子序列,不用合并。

综上,一趟归并排序的实现如下:

1
2
3
4
5
6
7
8
9
void MergePass(int a[],int n,int h){
int i = 1,k;
while(i <=n-2*h+1){ //待归并记录至少有两个长度为h的子序列
merge(a,i,i+h-1,i+2*h-1);
i = i + 2*h;
}
if(i<n-h+1)
merge(a,i,i+h-1,n); //子序列有一个长度小于h
}

问题3

开始时子序列长度为1,结束时长度为n,因此可以用有序序列的长度来作为结束的标志

1
2
3
4
5
6
7
void MergeSort2(int a[],int n){
int h = 1;
while(h<n){
MergePass(a,n,h);
h *=2;
}
}

复杂度分析

由二叉树性质可知,整个序列进行归并排序需要floor(log~2~n)次,将相邻长度为h的序列归并需要将这个序列扫一遍,需O(n)的时间,因此总的时间复杂度为O(nlog~2~n),这是归并排序的最好,最坏和平均时间性能。
在空间上,递归的写法需要log~2~n的栈空间,其中还有暂存归并结果的n个空间,所以递归的空间复杂度为O(n+log~2~n)。不过非递归的写法避免了递归中log~2~n的栈空间的使用,所以非递归的空间复杂度为O(n)。综上:用到归并排序时,最好用迭代方法


参考资料:
《数据结构——严蔚敏》
《大话数据结构——程杰》
《数据结构——从概念到C实现》