排序(7):归并排序

  • 5
  • 318 °C
  • A+
所属分类:算法基础
摘要

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

排序(7):归并排序

一、前言

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

二、算法思想

该算法采用经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

动态效果示意图:

排序(7):归并排序

分而治之:

1、分阶段

排序(7):归并排序

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。阶段可以理解为就是递归拆分子序列的过程,递归深度为logn。

2、治阶段

再来看看阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

排序(7):归并排序

排序(7):归并排序

3、代码

C++:

运行结果如下图所示:

排序(7):归并排序

可以看到已经可以看到归并排序算法顺利执行了。

Python:

运行效果同上。

三、算法分析

1、归并排序算法的性能

排序(7):归并排序

其中,log2n为以2为底,n的对数。

2、时间复杂度

归并排序的形式就是一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)

3、空间复杂度

由前面的算法说明可知,算法处理过程中,需要一个大小为n的临时存储空间用以保存合并序列。

4、算法稳定性

在归并排序中,相等的元素的顺序不会改变,所以它是稳定的算法。

5、归并排序和堆排序、快速排序的比较

若从空间复杂度来考虑:首选堆排序,其次是快速排序,最后是归并排序。

若从稳定性来考虑,应选取归并排序,因为堆排序和快速排序都是不稳定的。

若从平均情况下的排序速度考虑,应该选择快速排序。 

 

本站整理自:

http://www.cnblogs.com/jingmoxukong/p/4308823.html

https://www.cnblogs.com/chengxiao/p/6194356.html

Jack Cui
阿里云ECS

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:5   其中:访客  3   博主  2

    • avatar 蜗牛 来自天朝的朋友 谷歌浏览器 Windows 7 中国 移动 3

      华哥,这个C++的代码也是sublime text写的么?

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 联通

          @蜗牛 c++的用VS2015,这个 代码风格是sublime text看着舒服~

            • avatar 蜗牛 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学大学生城 3

              @Jack Cui 嗯呢,不错

          • avatar zyh 来自天朝的朋友 谷歌浏览器 Windows 10 河南省郑州市 联通 1

            python程序错了,第三十行判断应该是while i<=mid && j<=right:

              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学四舍(女生)

                @zyh 感谢指正,已更改。