专栏首页算法channel归并排序算法的过程图解

归并排序算法的过程图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注,让我们一起进步吧。

01

你会学到什么?

彻底弄明白常用的排序算法的基本思想,算法的时间和空间复杂度,以及如何选择这些排序算法,确定要解决的问题的最佳排序算法,已经总结了冒泡排序和其改进后的快速排序算法直接选择排序和堆排序算法,总结了直接插入排序到希尔排序做的改进,下面总结归并排序。

02

讨论的问题是什么?

各种排序算法的基本思想;讨论各种排序算法的时间、空间复杂度;以及算法的稳定性;算法是如何改进的,比如冒泡排序如何改进成了目前最常用的快速排序的,直接选择排序到堆排序的改进,直接插入排序到希尔排序做的优化,下面讨论归并排序。

03

相关的概念和理论

内部排序

若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。

外部排序

若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。

就地排序

若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),称为就地排序。

稳定排序

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序后,这些记录的相对次序保持不变,即在原序列中 ri=rj, ri 在 rj 之前,而在排序后的序列中,ri 仍在 rj 之前,则称这种排序算法是稳定的;否则称为不稳定的。

排序序列分布

排序需要考虑待排序关键字的分布情况,这会影响对排序算法的选择,通常我们在分析下列算法时都考虑关键字分布是随机分布的,不是按照某种规律分布的,比如正态分布等。

待排序序列

排序序列中,剩余即将要排序的序列部分。

已排序序列

排序序列中,已经排序好的序列部分。

04

归并排序

归并思想

归并排序,英文名称是MERGE-SORT。

它是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

算法的核心概念---二路归并

若将两个有序表合并成一个有序表,称为二路归并。

归并过程

  1. 比较 a[i] 和 b[j] 的大小,若 a[i]≤b[j],则将第一个有序表中的元素a[i]复制到 r[k] 中,并令i 和 k 分别加上1;否则将第二个有序表中的元素b[j]复制到r[k] 中,并令 j 和 k 分别加上1;
  2. 如此循环下去,直到其中一个有序表取完;
  3. 然后再将另一个有序表中剩余的元素复制到 r 中从下标 k 到下标t的单元。

这个过程,请见下面的例子演示。

二路归并例子演示

如下图所示,初始状态时,a序列[2,3,5]和b序列[2,9]为已排序好的子序列,现在利用二路归并,将a和b合并为有序序列 r,初始时,i指向a的第一个元素,j指向b的第一个元素,k初始值等于0。

说明,r中最后一个元素起到哨兵的作用,灰色显示。

第一步,比较a[i]和b[j],发现相等,如果规定相等时,a的先进入r,则如下图所示,i, k分别加1,为了形象化,归并后的元素不再绘制。

第二步,继续比较,此时b[j]小,所以b的元素2进入r,则如下图所示,j, k分别加1,

第三步,继续比较,此时a[i]小,所以a的元素3进入r,则如下图所示,i, k分别加1,

第四步,继续比较,此时a[i]小,所以a的元素5进入r,则如下图所示,i, k分别加1,此时序列a的3个元素已经归并完,b中还剩下一个,这个可以通过k可以看出,它还没有到达个数5。

第五步,将序列b中的所有剩余元素直接放入r中即可,不用做任何比较了,直至b变空,二路归并结束。

归并算法

归并排序的算法我们通常用递归实现。

  1. 先把待排序区间 [s,t] 以中点二分;
  2. 接着把左边子区间排序;
  3. 再把右边子区间排序;
  4. 最后把左区间和右区间用一次归并操作合并成有序的区间 [s,t] 。

归并排序的例子

我们仍然用冒泡排序和其改进后的快速排序算法直接选择排序和堆排序算法直接插入排序到希尔排序做的改进这三篇中用到的待排序列

3 2 5 9 2

归并排序的伪代码

sort(unsorted, start, end, sorted)
{
       if(start<end) {
            mid = start + (end-start)/2; //分隔区间
            sort(unsorted, start,mid,sorted); 
            sort(unsorted,mid+1,end,sorted);
           merge(unsorted,start,mid,end,sorted);
      }
}

下图演示的是归并排序递归版,第一次执行二路归并时的示意图,注意观察右图的栈的入栈顺序,

可以看到sort的入栈顺序,当执行一次merge时,一定是有2个sort返回并有序了,如下图,sort[0,0]和sort[1,1](递归返回的条件是start<end)都返回了,然后执行到merge,执行完merge后,sort[0,1]出栈,此时的栈顶为sort[0,2]函数,可以看出它的前半部分已经计算完,只需要计算后半部分,即第二个sort,然后再次merge,再sort[0,2]出栈。。。

如下为上个例子的归并排序的完整示例,sort 和 merge 的示意图,可以看到最后一次merge,正是上面说到的二路 [2,3,5] 和 [2,9] 的归并排序,如果不熟的,可以回过头再看看。

05

算法评价

归并排序的时间复杂度为O(nlogn) ,因为递归每次按照一半分区,并且merge需要线性时间。最重要的是该算法中最好、最坏和平均的时间性能都是O(nlogn)。

归并排序的空间复杂度为O(n),会占用内存。

总之,归并排序虽然比较占用内存,但却是一种效率高且稳定的算法。

06

总结

归并排序的时间复杂度,在最坏,最好和平均都是O(nlogn),这是效率,性能非常好的排序算法。

只不过它需要占用 O(n)的内存空间,如果数据量一旦很大,内存可能吃不消,这是它的弱点和致命伤。而其他排序算法,比如快速排序,希尔排序,都是就地排序算法,它们不占用额外的内存空间。

不过,这个占用内存的弱点,可以改进为就地排序,大家感兴趣,可以查看一下。

本文分享自微信公众号 - 算法channel(alg-channel),作者:alg-flody

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-10-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 直接选择排序到堆排序做的那些改进

    主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

    double
  • 学文科的他发明堆排序,逆袭成为斯坦福终身教授!

    计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了堆排序算法...

    double
  • 求两个有序数组合并后的中位数,最透讲解| 腾讯面试编程50题(三)

    本文是腾讯50道常考编程题之一:求解两个有序数组合并后的中位数,属于 "Hard" 难度,在校招中难倒一大波校招生。本文提供一种基本解法:基于归并排序。并对归并...

    double
  • 十大经典排序算法动画,看我就够了!

    而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    五分钟学算法
  • 常见排序算法分类

      此篇博客不讨论排序算法的思想,时间复杂度,空间复杂度,实现代码。只介绍常见排序算法有哪些,并按照什么进行分类。   排序算法分为两大类: 比较类...

    Dabelv
  • 两分钟真能搞懂桶排序

    在数据结构与算法的排序中,我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,算法的排序中,我...

    bigsai
  • 漫画:“排序算法” 大总结

    如果原始数组本来已经接近有序,只需要较少的比较交换次数即可完成排序。比如下面这个数组,只有7和8是逆序的:

    小灰
  • 涨姿势,图文带你了解 8 大排序算法

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    Java技术栈
  • 排序算法总括-java版

    内部排序就是仅仅依赖于内存就可以进行的排序,比如有交换排序、插入排序、选择排序、归并排序、基数排序

    shengjk1
  • 算法之排序(下)

    前面两篇文章说了时间复杂度为O(n2)的冒泡排序、插入排序和选择排序;也说了时间复杂度为O(nlogn)的归并排序和快速排序;这次来说一下时间复杂度为O(n)的...

    信安本原

扫码关注云+社区

领取腾讯云代金券