FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

[旧文整理]排序算法之归并排序(Merge Sort)

FunctionGHW posted @ 2013年9月23日 20:43 in 算法学习 with tags c merge sort in-place , 3022 阅读

归并排序(Merge Sort)是分治法的一个典型应用,相对于冒泡排序、插入排序和选择排序,其性能上有所提升,同时也是基于比较的排序算法中最好的算法之一。

归并排序的步骤如下:

  1. (Divide):将待排序序列(原问题)分成两个规模大致相等的子序列(子问题)
  2. (Conquer):递归地排序两个子序列,当子序列规模足够小的时候直接完成排序
  3. (Combine):合并两个已序的子序列得到原序列的排序结果
此算法中分解问题的过程类似于二分,关键步骤在合并。当分解出的子序列只有一个元素时,视为已序序列。

 

一般递归实现

排序算法如下,这段代码简单易懂,完全可以替代伪代码来说明算法的流程:

void merge_sort(int arr[], size_t size)
{
    if (size < 2)
    {
        return;
    }
    size_t mid = size >> 1;   //划分点

    merge_sort(arr, mid);           //递归地排序左子序列
    merge_sort(arr + mid, size - mid);//递归地排序右子序列

    merge(arr, size, mid);          //合并两个已序的子序列
}

                

此算法的核心--归并(Merge)步骤:

void merge(int arr[], size_t size, size_t mid)
{
    size_t lft_s = 0,   //左子序列起始点
           rit_s = mid, //右子序列起始点。左右两个子序列各自是已序的。
           pos = 0,
           i;

    //排序后存放结果的 临时数组,别忘了复制回原数组(arr[])!
    int* buf = (int*)malloc(size * sizeof(int));
    while (lft_s < mid && rit_s < size)
    {
        if (arr[lft_s] < arr[rit_s])
        {
            buf[pos++] = arr[lft_s++];
        }
        else
        {
            buf[pos++] = arr[rit_s++];
        }
    }
    while (lft_s < mid)//左子序列有剩余元素
    {
        buf[pos++] = arr[lft_s++];
    }
    while (rit_s < size)//右子序列有剩余元素
    {
        buf[pos++] = arr[rit_s++];
    }
    //排序结果放回原数组
    for (i = 0; i < size; ++i)
    {
        arr[i] = buf[i];
    }
    free(buf);//不要忘记释放临时空间。
}
                

归并排序的递归分解过程就是个"二分"的过程,因此其时间复杂度为\(O(\log n)\),而Merge函数的时间复杂度是\(O(n)\),因此整个算法的复杂度是\(O(n\log n)\),略过证明。最后注意因为Merge里用到了额外的内存空间,因此这里有个\(O(n)\)的空间开销。

原地归并排序(In-place Merge Sort)

对于较大规模的输入,归并排序所需要的\(O(n)\)级别的空间开销还是很恶心的,这也是归并排序的一个软肋。在《数据结构基础(C语言版)(第2版)》第7章介绍了一种不需要额外空间开销的归并算法--原地归并,但是其算法比较复杂,我看了许久才勉强理解。不过Google一下会发现有另外一种原地算法,基于手摇法的版本,这个版本的必要容易理解。

首先看一个在《编程珠玑》中看到的神奇算法--手摇法,其功能是交换两个相邻子序列的位置而保持每个子序列内部的排序不变,如果你不理解请单机测试一下,很好玩的。

//此函数用于一个反转数组
void reverse(int arr[], size_t size) {
    int left = 0,
        right = size - 1,
        tmp = 0;
    while(left < right)
    {
        tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}

//手摇法 通过三次反转操作交换两个子序列的位置,两个子序列内部的排序不变。
void swap_blocks(int arr[], size_t size, size_t lft_size) {
    reverse(arr, lft_size);
    reverse(arr + lft_size, size - lft_size);
    reverse(arr, size);
}
                

原地归并的实现:

void in_place_merge(int arr[], size_t size, size_t mid)
{
    size_t lft_s = 0, rit_s = mid, rmove;

    while (lft_s < rit_s && rit_s < size)
    {
        while (lft_s < rit_s && arr[lft_s] <= arr[rit_s])
        {
            lft_s++;
        }
        rmove = 0;
        while (rit_s < size && arr[lft_s] > arr[rit_s])
        {
            rmove++;
            rit_s++;
        }
        swap_blocks(arr + lft_s, rit_s - lft_s, rit_s - lft_s - rmove);
        lft_s += rmove;
    }
}
                

具体的分析过程我懒得叙述了,挺麻烦的。可以参考这篇文章,结合图片应该能够看懂。

旧文链接

其实这篇文章是重新写的,和所谓的"旧文"没什么关系了,旧文只有一段烂代码,所以不看也罢。贴个链接为了方便自己对比吧。
合并排序 MergeSort, 终于自己做出来了

最后推荐一篇关于优化归并排序的文章,有兴趣的去看看:归并排序利用插入排序优化


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter