算法进化历程之“归并排序”
算法进化历程之“归并排序”巧若拙（欢迎转载，但请注明出处：http://blog.）
归并排序是分治算法的典型运用，其中先分治，再合并的思路真是美妙至极。
归并排序算法的基本操作是合并两个已排序的表，这只需要线性的时间，不足之处是需要分配一个临时数组来暂存数据。
归并排序算法可以用递归的形式实现，形式简洁易懂。如果N=1，则只有一个元素需要排序，我们可以什么都不做；否则，递归地将前半部分数据和后半部分数据各自归并排序，然后合并这两个部分。
归并排序算法也可以用非递归的形式实现，稍微难理解一点。它刚好是递归分治算法的逆向思维形式，在使用递归分治算法时，程序员只需考虑将一个大问题分成若干个形式相同的小问题，和解的边界条件，具体如何解决这些小问题是由计算机自动完成的；而非递归形式要求程序员从最基本的情况出发，即从解决小问题出发，一步步扩展到大问题。
一点说明：很多人在写递归形式的归并排序算法时，临时数组是在归并排序子程序 MSort ()中分配的，这使得 在任一时刻都可能有 logN 个临时数组处在活动期，如果数据较多，则开销很大，实用性很差 。我在版本1中把临时数组设置在合并函数 Merge ()中，避免了这个问题；在版本2中进一步优化，把临时数组设置在归并排序驱动程序MergeSort()中，只需执行一次分配空间的函数就行了。
版本一：普通的合并算法
网络上贴出的归并排序算法版本很多，多数采用的普通的合并函数 Merge ()，即先将存储在A[]中的两个已排序序列按非递减序归并入tempA[]，然后将A[]中剩余的元素复制到tempA[]，最后将tempA[]中元素复制回A[]。算法简明易懂，代码如下：
void MergeSort_1(ElemType A[], int n)//归并排序驱动程序
{
MSort_1(A, 0, n-1);
}
void MSort_1(ElemType A[], int left, int right)//归并排序子程序
{
int mid = (left + right) / 2;
if (left < right)
{
MSort_1(A, left, mid);
MSort_1(A, mid+1, right);
Merge_1(A, left, mid, right);
}
}
void Merge_1(ElemType A[], int left, int mid, int right)//普通合并程序
{
int i, j, k;
ElemType *tempA = malloc((right-left+1)*sizeof(ElemType));
if (!tempA)
{
printf("Out of space!");
exit (1);
}
k = 0;
for (i=left, j=mid+1; i<=mid && j<=right; )//将A[]中元素按非递减序归并入tempA[]
{
if (A[i] <= A[j])
tempA[k++] = A[i++];
else
tempA[k++] = A[j++];
}
//将A[]中剩余的元素复制到tempA[]
while (i <= mid)
tempA[k++] = A[i++];
while (j <= right)
tempA[k++] = A[j++];
//将tempA[]中元素复制回A[]
for (i=left,j=0; j<k; i++,j++)
A[i] = tempA[j];
free(tempA);
}
版本二：高效的合并算法
Mark Allen Weiss在其著作《数据结构与算法分析——C语言描述》中介绍了一个高效的归并排序算法，他把临时数组设置在归并排序驱动程序MergeSort()中，只需执行一次分配空间的函数就行了。
此外，还可以对普通的合并函数进行优化，只需把两个已排序序列“相向复制”到临时数组tempA[]，然后归并入A[]即完成排序。所谓“相向复制”是指第一个序列顺序存储到tempA[]，第二个序列逆序存储到tempA[]；执行合并操作的时候从左向右扫描序列1，从右向左扫描序列2，正好“相向而行”。这样处理的好处是无需判断两个分序列是否越界，只要合并完所有元素，循环自动结束。
代码如下：
void MergeSort_2(ElemType A[], int n)//归并排序驱动程序
{
ElemType *tempA = malloc(n*sizeof(ElemType));
if (!tempA)
{
printf("Out of space!");
exit (1);
}
MSort_2(A, tempA, 0, n-1);
free(tempA);
}
void MSort_2(ElemType A[], ElemType tempA[], int left, int right)//归并排序子程序
{
int mid = (left + right) / 2;
if (left < right)
{
MSort_2(A, tempA, left, mid);
MSort_2(A, tempA, mid+1, right);
Merge_2(A, tempA, left, mid, right);
}
}
void Merge_2(ElemType A[], ElemType tempA[], int left, int mid, int right)//高效合并程序
{
int i, j, k;
for (i=left; i<=mid; i++)//将A[left..mid]中元素顺序复制到tempA[left..mid]
tempA[i] = A[i];
for (i=mid+1,j=right; i<=right; i++,j--)//将A[mid+1..right]中元素逆序序复制到tempA[mid+1..right]
tempA[j] = A[i];
for (k=i=left, j=right; k<=right; )//巧妙安排扫描方向，只需判断k是否越界
{
if (tempA[i] <= tempA[j])
A[k++] = tempA[i++];
else
A[k++] = tempA[j--];
}
}
版本三：非递归算法
归并排序的递归算法简明易懂，但毕竟要多次递归调用，需要额外的递归栈空间，效率不如非递归算法高。
网络上各种非递归算法也是五花八门，良莠不齐，我就不一一介绍了，只贴出我最喜欢的一款——也是原创的一款，呵呵。
简单介绍一下算法思路：分别用beforeLen和afterLen表示合并前后序列的长度，其中合并后序列的长度是合并前的两倍。
初始条件beforeLen=1，之后每执行一次合并操作，beforeLen增倍（beforeLen=afterLen）。
外部 for 循环的循环体每执行一次，都使 beforeLen 和 afterLen 加倍。内部的for循环执行序列的合并工作，它的循环体每执行一次，i 都向前移动 afterLen 个位置，合并相邻的两个等量序列，直到剩余元素的数量小于afterLen。若剩下的元素数量介于beforeLen和afterLen之间，说明这是两个数量不等的序列，对他们进行合并操作；若剩下的元素数量不多于beforeLen，说明这些元素属于同一个已排序的序列，无需合并。
合并函数采用了高效的Merge_2()。代码如下：
void MergeSort_3(ElemType A[], int n)//归并排序主程序（非递归）
{
int i, c=0;
int beforeLen; // 合并前序列的长度
int afterLen = 1;// 合并后序列的长度
ElemType *tempA = malloc(n*sizeof(ElemType));
if (!tempA)
{
printf("Out of space!");
exit (1);
}
for (beforeLen=1; afterLen<n; beforeLen=afterLen)
{
afterLen = beforeLen << 1; //合并后序列的长度是合并前的两倍
for (i=0; i+afterLen<=n; i+=afterLen) //两两合并相邻的两个等量序列
Merge_2(A, tempA, i, i+beforeLen-1, i+afterLen-1);
if (i+beforeLen < n)//合并两个数量不等的序列
Merge_2(A, tempA, i, i+beforeLen-1, n-1);
}
free(tempA);
}
本篇文章中的Merge_2()和MergeSort_3()均属原创，虽然经过小规模数据的测试，但也可能存在纰漏，欢迎批评指正，谢谢！
[ 本帖最后由 巧若拙 于 2014-10-18 11:32 编辑 ]
