FunctionGHW

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

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

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

归并排序(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, 终于自己做出来了

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

Small_feed 评论 (34)
1
[回复]
Liwovosa 说:
2021年4月22日 16:53

Superior post, keep up with this exceptional work. It's nice to know that this topic is being also covered on this web site so cheers for taking the time to discuss this! Thanks again and again! solarmovies

2
[回复]
Liwovosa 说:
2021年4月25日 16:36

I have recently started a blog, the info you provide on this site has helped me greatly. Thanks for all of your time & work. doglotto.wix.biz

3
[回复]
Liwovosa 说:
2021年4月27日 17:45

i was just browsing along and came upon your blog. just wanted to say good blog and this article really helped me. สมัครFIFA55

4
[回复]
Liwovosa 说:
2021年4月28日 16:50 This particular is usually apparently essential and moreover outstanding truth along with for sure fair-minded and moreover admittedly useful My business is looking to find in advance designed for this specific useful stuffs… uwynn888.com
5
[回复]
jackjohnny 说:
2021年5月01日 17:44

I'm glad I found this web site, I couldn't find any knowledge on this matter prior to.Also operate a site and if you are ever interested in doing some visitor writing for me if possible feel free to let me know, im always look for people to check out my web site. disney+ generatordisney+ accounts

6
[回复]
jackjohnny 说:
2021年5月06日 17:59

Thank you for taking the time to publish this information very useful! Visto turistico per l'India

7
[回复]
jackjohnny 说:
2021年5月11日 19:38

Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you. how to get free bp and uc in pubg

8
[回复]
play club casino 说:
2021年5月12日 19:06

Say you got a nice blog post. Much thanks again. Really Great.<a href="https://cutt.ly/GbFziWP">http://www.gewinnspielautomaten.com/</a>

9
[回复]
play club casino 说:
2021年5月12日 19:07

Say you got a nice blog post. Much thanks again. Really Great.[url=https://cutt.ly/GbFziWP]http://www.gewinnspielautomaten.com/[/url]

10
[回复]
jackjohnny 说:
2021年5月20日 16:03

I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work. how to earn money 200 per day

11
[回复]
online blackjack 说:
2021年6月11日 00:38

I truly appreciate this post. Really looking forward to read more. Fantastic.

12
[回复]
jackjohnny 说:
2021年6月11日 04:18

This is my first time i visit here. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here keep up the good work Citronella oil Manufacturers in India

13
[回复]
jackjohnny 说:
2021年6月17日 18:41

What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much. coin master hack

14
[回复]
jackjohnny 说:
2021年6月18日 00:24

Nice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post. 먹튀사이트

15
[回复]
jackjohnny 说:
2021年6月20日 19:44

thanks for this usefull article, waiting for this article like this again. Free Diamonds Generator

16
[回复]
jackjohnny 说:
2021年6月24日 16:09

I was surfing the Internet for information and came across your blog. I am impressed by the information you have on this blog. It shows how well you understand this subject. Towelsforthebeach.com

17
[回复]
jackjohnny 说:
2021年6月26日 22:53

Thank you for the update, very nice site.. <a href="https://totoboyna.com/">안전놀이터</a>

18
[回复]
spielautomaten-deuts 说:
2021年6月27日 20:19

Major thanks for the blog post. Really thank you! Keep writing.

19
[回复]
jackjohnny 说:
2021年6月29日 23:28

thanks for the tips and information..i really appreciate it.. new zealand tourist visa

20
[回复]
arkseo 说:
2021年7月05日 03:46

Your work is truly appreciated round the clock and the globe. It is incredibly a comprehensive and helpful blog. how to become a payment service provider

21
[回复]
arkseo 说:
2021年7月06日 12:19

Very good points you wrote here..Great stuff...I think you've made some truly interesting points.Keep up the good work. Free Robots.txt Generator Tool

22
[回复]
spielautomaten deuts 说:
2021年7月10日 20:07

Great thanks for sharing this blog post. Thanks Again. Keep writing.

23
[回复]
jackjohnny 说:
2021年7月13日 18:19

Positive site, where did u come up with the information on this posting? I'm pleased I discovered it though, ill be checking back soon to find out what additional posts you include. Brawl Stars Hack 2021

24
[回复]
jackjohnny 说:
2021年7月14日 19:59

ikinci el cikma enjektör bosch kullanilmis oto enjektör satin al ikinci el enjektör

25
[回复]
spielautomaten-deuts 说:
2021年7月19日 02:10

Very neat blog post. Really thank you! Will read on...

26
[回复]
spielautomaten 说:
2021年7月28日 19:27

Major thanks for the blog article. Really looking forward to read more. Really Cool.

27
[回复]
casino portal 说:
2021年8月01日 19:27

Major thanks for the article. Thanks Again.

28
[回复]
aman 说:
2021年8月18日 21:38

Really great post. I enjoy reading this article. There is such a true article there is more information for us.
<a href="https://4anime.click/">4anime</a>

29
[回复]
aman 说:
2021年8月18日 21:40

Thanks for sharing this lovely post. https://4anime.click/

30
[回复]
Arkseo 说:
2021年8月30日 13:32

I haven’t any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us. Good Search

31
[回复]
Arkseo 说:
2021年9月04日 14:37

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with extra information? It is extremely helpful for me. merchant services job description

32
[回复]
aman 说:
2021年9月28日 19:50

I read that Post and got it fine and informative. <a href="https://9anime.surf/">9ANIME</a>

33
[回复]
download instagram r 说:
2021年10月06日 21:20

Thank you for your article post. Really thank you! Cool.

34
[回复]
Hamza 说:
2022年12月10日 01:36

We at this point strategy it's rather a view to share with you could everyone more was enduring problem analyzing while The small business is usually a little inconclusive plainly seemed to be allowed to healthy artists together with refers to having in this posting. more info


登录 *


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

计数器

91579

FunctionGHW

搜索

分类

博客链接

我的饭否

热门文章

最新评论

RSS

RSS Link
designed by: Website Builder | coded by: Web Hosting Geeks | Host by is-Programmer.com | Power by Chito 1.3.3 beta