归并排序

作者:柳行刚

编辑:徐 松

基本思想

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

将待排序序列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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

411
来自专栏WOLFRAM

错觉艺术的巅峰,错觉图形大师M.C. Escher的不可能方块的可能模型

1333
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5866
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9664
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2152
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1152
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1471
来自专栏WOLFRAM

向日葵中的数学之美

1823

扫码关注云+社区