排序算法之归并排序
罗朝辉(http://www.cppblog.com/kesalin)
转载请注明出处
排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重,其重要性勿需多言。下文将介绍常用的如下排序方法,对它们进行简单的分析和比较,并提供 C 语言实现。
所谓排序,就是要将一堆记录,使之按关键字递增(或递减)次序排列起来。根据排序所采用的策略,可以分为如下五种:
1、插入排序(直接插入排序、希尔排序)
2、交换排序(冒泡排序、快速排序)
3、选择排序(直接选择排序、堆排序)
4、归并排序;
5、桶排序(桶排序,基数排序);
---------------------------------------------------------------------------------
前面讲了插入排序,交换排序,选择排序,下面接着来讲归并排序。
归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。
归并排序
基本思想:设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上:array[low..m],array[m + 1..high],先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中,待合并完成后将 temp 复制回 array[low..high]中,从而完成排序。
在具体的合并过程中,设置 i,j 和 p 三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字,取关键字较小(或较大)的记录复制到 temp[p] 中,然后将被复制记录的指针 i 或 j 加 1,以及指向复制位置的指针 p 加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空),此时将另一非空的子序列中剩余记录依次复制到 array 中即可。
下面是合并过程的 C 代码实现:
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void merge(int* array, int low, int mid, int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
assert(array && low >= 0 && low <= mid && mid <= high);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int* temp = (int*)malloc((high - low + 1) * sizeof(int));
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (!temp)
{
printf("Error:out of memory!");
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i = low;
int j = mid + 1;
int index = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (i <= mid && j <= high)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (array[i] <= array[j])
{
temp[index++] = array[i++];
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
temp[index++] = array[j++];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (i <= mid)
{
temp[index++] = array[i++];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (j <= high)
{
temp[index++] = array[j++];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
memcpy((void*)(array + low), (void*)temp, (high - low + 1) * sizeof(int)) ;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
free(temp);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
归并排序有两种实现方法:自底向上和自顶向下。
自底向上方法,也就是常说的二路归并排序,其基本思想是:第 1 趟排序将长度为 n 的待排序记录看作 n 个长度为 1 的有序子序列,然后将这些子序列两两合并。完成第 1 趟排序之后,将得到 lgn 个长度为 2 的有序子序列(如果 n 为奇数,则最后还有一个长度为 1 的子序列)。第 2 趟排序是在第 1 趟的排序的基础上,将这 lgn 个长度为 2 的子序列两两合并。如此反复,直到最后得到一个长度为n的有序文件为止。从这个排序过程来看,二路归并排序是从将长度为 1 的子序列排序变化到长度为 n 的有序序列,因而是自底向上的。
下面是二路归并排序的 C 代码实现:
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 对 [0, length - 1] 做一趟归并长度为 n 的归并排序
void merge_pass(int* array, int length, int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
assert(array && length >= 1 && n >= 1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
int sortLength = 2 * n;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// 归并长度为 n 的两个相邻子序列
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i + sortLength - 1 < length; i = i + sortLength)
{
merge(array, i, i + n - 1, i + sortLength - 1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// 若 i + n - 1 < length - 1,则剩余一个子文件轮空,无须归并。
// 尚有两个子序列,其中后一个长度小于 n, 归并最后两个子序列。
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (length - 1 > i + n - 1)
{
merge(array, i, i + n - 1, length - 1);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 用分治法自下向上进行二路归并排序
//
void merge_sort(int* array, int length)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
assert(array && length >= 0);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(n = 1; n < length; n = (n << 1))
{
merge_pass(array, length, n);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
自底向上的二路归并排序算法虽然效率较高,但可读性较差(循环实现比递归实现一般效率都要高些)。下面来看看自上而下的递归实现,其可读性要好得多。自上而下的方法是采用分治法思想,具体排序过程分成三个过程:
(1)分解:将当前区间一分为二,即求分裂点 mid = (low + high)/2;
(2)求解:递归地对两个子区间 array[low..mid] 和 array[mid + 1..high] 进行归并排序;递归的终结条件:子区间长度为 1(一个记录自然有序)。
(3)合并:将已排序的两个子区间R[low..mid]和R[mid + 1..high]归并为一个有序的区间 array[low..high]。
下面即是自上而下方法的 C 代码实现:
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void merge_sort_dc_impl(int* array, int low, int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
assert(array && low >= 0);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int mid;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (low < high)
{
mid = (low + high) >> 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
merge_sort_dc_impl(array, low, mid);
merge_sort_dc_impl(array, mid + 1, high);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
merge(array, low, mid, high);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 用分治法自上向下进行排序
void merge_sort_dc(int* array, int length)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
assert(array && length >= 0);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
merge_sort_dc_impl(array, 0, length - 1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
时间复杂度分析:
对长度为 n 的序列进行 lgn 趟二路归并,而每一趟归并的时间复杂度为 O(n),因此归并排序的平均时间复杂度为 nlgn。
空间复杂度分析:
需要与待排记录等大的空间来存储中间变量,因为其空间复杂度为 O(n)。因此,归并排序肯定就不是就地排序了。
补充:
归并排序是稳定排序。若归并排序采用链表存储结构的话,实现起来更加高效。
=======================================================================================
测试:
在前文《排序算法之插入排序》测试代码的基础上添加两行代码即可:
{"合并排序:自下向上二路归并", merge_sort}, {"合并排序:自上向下分治", merge_sort_dc},
运行结果如下:
=== 合并排序:自下向上二路归并 ===
original: 65 32 49 10 8 72 27 42 18 58 91
sorted: 8 10 18 27 32 42 49 58 65 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
sorted: 0 1 2 3 4 5 6 7 8 9 10
=== 合并排序:自上向下分治 ===
original: 65 32 49 10 8 72 27 42 18 58 91
sorted: 8 10 18 27 32 42 49 58 65 72 91
original: 10 9 8 7 6 5 4 3 2 1 0
sorted: 0 1 2 3 4 5 6 7 8 9 10