归并排序

作者:柳行刚

编辑:徐 松

基本思想

归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列

再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

关键点

我们总结一下归并排序其实就只有两步:

分解:将有序序列不断地分裂,直到每个区间都只有一个数据为止。

合并:将两个区间合并为一个有序区间,一直合并直到只有一个区间为止。

其实分解的过程我们很容易想明白的,用递归就可以。但是我们今天最主要的步骤是合并,你要将两个区间合并为一个有序的区间你会怎么思考呢?

这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

代码实现

其实我们发现这种做法效率其实还是蛮高的,效率达到了O(N).现在我们解决了合并的问题。

现在总的来看一下归并排序的做法,通过先递归的分解数列(将数列分解成只有一个元素的区间),再合并数列就完成了归并排序。

总结

归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。

算法名称

最差时间复杂度

平均时间复杂度

最优时间复杂度

空间复杂度

稳定性

归并排序

O(NlogN)

O(NlogN)

O(NlogN)

O(n)

稳定

小提示

所有排序当中用的最多的是 堆排序,快速排序,归并排序.

若从空间复杂度来考虑:

首选堆排序,其次是快速排序,最后是归并排序。

若从稳定性来考虑:

应选取归并排序,因为堆排序和快速排序都是不稳定的。

若从平均情况下的排序速度考虑:

应该选择快速排序。

理解了归并排序算法了吗?

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-08-31

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

爬楼梯问题

假设你现在正在爬楼梯,楼梯有 n 级。每次你只能爬 1 级或者 2 级,那么你有多少种方法爬到楼梯的顶部?

271
来自专栏小詹同学

程序员面试必备之排序算法汇总(上)

希望小小詹同学学习同时能便于他人~ ---- 本文用Python实现了快速排序、插入排序、希尔排序、归并排序、堆排序、选择排序、冒泡排序共7种排序算法。 ? ...

3557
来自专栏前端小叙

javaScript实现归并排序

归并排序是一个O(nlogn)的算法,其基本思想就是一个分治的策略,先进行划分,然后再进行合并,下面举个例子。有这样一组数据: {5,4,1,22,12...

3188
来自专栏Golang语言社区

Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法。...

33810
来自专栏向治洪

算法笔记之排序

最近在看《算法笔记》,如果单从算法来说,这本书真正做到了短小精悍,首先以排序入题,那么我们今天也来说说排序。 排序 将一堆杂乱无章的元素按照某种规则有序排列的过...

19610
来自专栏静默虚空的博客

排序七 归并排序

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

1707
来自专栏jeremy的技术点滴

排序算法python实现

3188
来自专栏互联网杂技

排序算法性能比较

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

3287
来自专栏Java 源码分析

八大排序算法

​ 八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。 冒泡排序...

3193
来自专栏编程

八大排序算法的 Python 实现!

今天CoCo酱给大家介绍一下关于八大排序算法的Python实现,对八大排序算法进行详细描述和代码实现,下面我们一起来看一下吧。 1、插入排序 描述: 插入排序的...

1897

扫描关注云+社区