归并排序（Merging Sort）
归并（Merging）：将两个排好序的文件合并成一个更大的排好序的文件！时间复杂度是O(n)
选择（Selection）：将一个文件平均拆分成两个独立的文件！
归并排序主要包括两个步骤：选择（Selection）和归并（Merging），利用的是分治的思想;首先将文 件平均拆分成两个部分，对这两个部分分别进行排序，然后归并两个部分组成一个排好序的文件。
归并排序的特性：
（1）对N个元素的文件进行排序，它的运行时间与NlogN 成比例，与输入数据无关；
（2）如果使用的归并算法是稳定的，则归并排序是稳定；
（3）归并排序使用与N成正比的额外内存空间；
两路归并（Two-Way Merging）
对两个已排序的文件，可以简单地将他们合并成一个排好序的文件，分别取两个输入文件中最小的数据，将这两个数据中较小的数放到输出文件中，循环操作，直到两个输入文件的数据项都已输出。该操作的运行时间是输出元素数目的线性函数；
首先考虑一个简单的问题：如何在线性的时间内将两个有序队列合并为一个有序队列（并输出）？
A队列：1 3 5 7 9
B队列：1 2 7 8 9
看上面的例子，AB两个序列都是已经有序的了。在给出数据已经有序的情况下，我们会发现很多神奇的事，比如，我们将要输出的第一个数一定来自于这两个序列各自最前面的那个数。两个数都是1，那么我们随便取出一个（比如A队列的那个1）并输出：
A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1
注意，我们取出了一个数，在原数列中删除这个数。删除操作是通过移动队首指针实现的，否则复杂度就高了。
现在，A队列打头的数变成3了，B队列的队首仍然是1。此时，我们再比较3和1哪个大并输出小的那个数：
A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1 1
接下来的几步如下：
A队列：1 3 5 7 9 A队列：1 3 5 7 9 A队列：1 3 5 7 9 A队列：1 3 5 7 9
B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ==> B队列：1 2 7 8 9 ……
输出：1 1 2 输出：1 1 2 3 输出：1 1 2 3 5 输出：1 1 2 3 5 7
我希望你明白了这是怎么做的。这个做法显然是正确的，复杂度显然是线性。
归并排序(Merge Sort)将会用到上面所说的合并操作。给出一个数列，归并排序利用合并操作在O(nlogn)的时间内将数列从小到大排序。归并排序用的是分治(Divide and Conquer)的思想。首先我们把给出的数列平分为左右两段，然后对两段数列分别进行排序，最后用刚才的合并算法把这两段（已经排过序的）数列合并为一个数列。有人会问“对左右两段数列分别排序时用的什么排序”么？答案是：用归并排序。也就是说，我们递归地把每一段数列又分成两段进行上述操作。你不需要关心实际上是怎么操作的，我们的程序代码将递归调用该过程直到数列不能再分（只有一个数）为止。
初看这个算法时有人会误以为时间复杂度相当高。我们下面给出的一个图将用非递归的眼光来看归并排序的实际操作过程，供大家参考。我们可以借助这个图证明，归并排序算法的时间复杂度为O(nlogn)。
[3] [1] [4] [1] [5] [9] [2] [7]
\ / \ / \ / \ /
[1 3] [1 4] [5 9] [2 7]
\ / \ /
[1 1 3 4] [2 5 7 9]
\ /
[1 1 2 3 4 5 7 9]
上图中的每一个“ \ / ”表示的是上文所述的线性时间合并操作。上图用了4行来图解归并排序。如果有n个数，表示成上图显然需要O(logn)行。每一行的合并操作复杂度总和都是O(n)，那么logn行的总复杂度为O(nlogn)。这相当于用递归树的方法对归并排序的复杂度进行了分析。假设，归并排序的复杂度为T(n)，T(n)由两个T(n/2)和一个关于n的线性时间组成，那么T(n)=2*T(n/2)+O(n)。不断展开这个式子我们可以同样可以得到T(n)=O(nlogn)的结论，你可以自己试试。如果你能在线性的时间里把分别计算出的两组不同数据的结果合并在一起，根据T(n)=2*T(n/2)+O(n)=O(nlogn)，那么我们就可以构造O(nlogn)的分治算法。这个结论后面经常用。我们将在计算几何部分举一大堆类似的例子。
如果你第一次见到这么诡异的算法，你可能会对
这个感兴趣。分治是递归的一种应用。这是我们第一次接触递归运算。下面说的快速排序也是用的递归的思想。递归程序的复杂度分析通常和上面一样，主定理(Master Theory)可以简化这个分析过程。主定理和本文内容离得太远，我们以后也不会用它，因此我们不介绍它，大家可以自己去查。有个名词在这里的话找学习资料将变得非常容易，我最怕的就是一个东西不知道叫什么名字，半天找不到资料。
归并排序有一个有趣的副产品。利用归并排序能够在O(nlogn)的时间里计算出给定序列里逆序对的个数。你可以用任何一种平衡二叉树来完成这个操作，但用归并排序统计逆序对更方便。我们讨论逆序对一般是说的一个排列中的逆序对，因此这里我们假设所有数不相同。假如我们想要数1, 6, 3, 2, 5, 4中有多少个逆序对，我们首先把这个数列分为左右两段。那么一个逆序对只可能有三种情况：两个数都在左边，两个数都在右边，一个在左一个在右。在左右两段分别处理完后，线性合并的过程中我们可以顺便算出所有第三种情况的逆序对有多少个。换句话说，我们能在线性的时间里统计出A队列的某个数比B队列的某个数大有多少种情况。
A队列：1 3 6 A队列：1 3 6 A队列：1 3 6 A队列：1 3 6 A队列：1 3 6
B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ==> B队列：2 4 5 ……
输出： 输出：1 输出：1 2 输出：1 2 3 输出：1 2 3 4
每一次从B队列取出一个数时，我们就知道了在A队列中有多少个数比B队列的这个数大，它等于A队列现在还剩的数的个数。比如，当我们从B队列中取出2时，我们同时知道了A队列的3和6两个数比2大。在合并操作中我们不断更新A队列中还剩几个数，在每次从B队列中取出一个数时把当前A队列剩的数目加进最终答案里。这样我们算出了所有“大的数在前一半，小的数在后一半”的情况，其余情况下的逆序对在这之前已经被递归地算过了。
二路归并的简单代码示例：
template <class Item>
void mergeAB(Item c[],Item a[],int N,Item b[], int M){
for(int i=0,j=0,k=0;k<N+M;k++){
if(i==N){
c[k] = b[j++];
continue;
}
if(j==M){
c[k] = a[i++];
continue;
}
c[k] = (a[i]<b[j])?a[i++]:b[j++];
}
} |
抽象原地归并算法(Abstract In-Place Merge)
基本归并算法的不足：基本归并算法中值得注意的特性是内部循环中包括了两个测试操作，这两个操作判断对连个输入数组访问是否已到了结尾。当然，这两个测试通常得到的是失败的信息，这种情况下，就可以改用标志关键字代替测试操作。
改进：我们可以在数组a和辅助数组的最后加上一个包含比其他关键字都要大的关键字的数据项时，就可以除去测试操作，因为当数组a(b)访问完后，该标志使下一个要加入数组c的元素一定是从数组b(a)中取出，直到完成了整个合并操作。但有时很难使用标志关键字的，因为可能很难确定标志关键字的值或不够存储空间使用标志关键字。
但对归并操作，有一个简单转换，基本思路如下：要复制数组来来执行原地归并排序，只需简单讲第二个数组变成倒序，因此相关的指针从右移向左，这样的安排使最大的元素成为了标志关键字----不管实际在哪个
数组
代码示例如下：
template <class Item>
void merge(Item a[],int l,int m, int r){
int i,j;
static Item aux[maxN];
for(i=m+1;i<l;i--){
aux[i-1]=a[i-1];
}
for(j=m;j<r;j++){
aux[r+m-j]=a[j+1];
}
for(int k=l;k<=r;k++){
if(aux[j]<aux[i])
a[k]=aux[j--];
else
a[k]=aux[i++];
}
} |
自顶向下的归并排序(Top—Down Mergesort)
基本的归并排序是一个基本的分治法的递归程序，通过将数组a[1],....,a[r]分成两部分a[1],....,a[m]和a[m+1],....,a[r]，然后分别对它们进行排序（利用递归调用，利用归并排序），然后将得到的已排序的文件合并，得到最终的排序文件
代码如下：
template <class Item>
void mergesort(Item a[],int l,int r){
if(r<=l)
return;
int m=(r+l)/2;
mergesort(a,l,m);
mergesort(a,m+1,r);
merge(a,l,m,r);
} |
归并排序的特性：
（1）对N个元素的文件进行排序，它的运行时间与NlogN 成比例，与输入数据无关；
（2）如果使用的归并算法是稳定的，则归并排序是稳定；
（3）归并排序使用与N成正比的额外内存空间；
对基本归并排序算法的改进
（1）对小的子文件进行插入排序，可以使典型的归并排序的运行效率提高10%-15%
（2）先为数组做一个备份，然后使用mergeAB()，通过转换递归调用中的变量，消除外部的数组复制操作，可以节省将数组复制到辅助数组所花的时间；
代码如下：
template <class Item>
void mergesortABr(Item a[], Item b[],int l,int r){
if(r-l<=10){
InsertSort(a,l,r);
return ;
}
int m = (l+r)/2;
mergesortABr(b,a,l,m);
mergesortABr(b,a,m+1,r);
mergeAB(a+l,b+l,m-l+1,b+m+1,r-m);
}
template <class Item>
void mergesortAB(Item a[],int l,int r){
static Item aux[maxN];
for(int i=l;i<=r;i++)
aux[i]=a[i];
mergesortABr(a,aux,l,r);
} |
自底向上的归并排序(Bottom-Up Mergesort) 即是非递归的归并排序
代码如下：
inline int min(int A,int B){
return (A<B) ? A:B;
}
template <class Item>
void mergesortBU(Item a[],int l,int r){
for(int m-1;m<r-l;m=2*m)
for(int i=l;i<=r-m;i+=2*m)
merge(a,i,i+m-1,min(i+m+m-1,r));
} |
例子如下：
A S O R T I N G E X A M P L E
A S
O R
I T
G N
E X
A M
E L
A O R S
G I N T
A E M X
E L P
A G I N O R S T
A E E L M P X
A A E E G I L M N O P R S T X
归并排序的性能特性
阅读(3108) | 评论(0) | 转发(0) |
