归并排序

作者:柳行刚

编辑:徐 松

基本思想

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

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

相关文章

来自专栏mathor

波兰表达式

894
来自专栏编程理解

排序算法(四):归并排序

归并排序是通过分治的方式,将待排序集合拆分为多个子集合,对子集合排序后,合并子集合成为较大的子集合,不断合并最终完成整个集合的排序。

1171
来自专栏我是东东强

常见算法之排序

各类排序算法,不仅是算法基本功,也是面试中永恒的考题,关于每种算法思想、实现(递归与非递归)以及时空复杂度分析是必须牢牢把握的送分题。本文先将排序算法按不同标准...

1002
来自专栏尾尾部落

普林斯顿大学算法公开课笔记——插入排序

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

1051
来自专栏Python疯子

数据分析之numpy

ndarray概述 创建n维数组 接收的是列表类型,所有元素类型必须相同 shape表示各维度大小的元组 dtype表示数组数据类型对象

1081
来自专栏云霄雨霁

子字符串查找----Boyer-Moore算法(从右向左匹配)

1080
来自专栏PHP在线

分享 mysql 强大的函数

一、数学函数 //返回x的绝对值 abs(x) select abs(-1) // 1 //返回x的二进制(oct返回八进制,hex返回十六进制...

3328
来自专栏从零开始的linux

python运算符

算数运算符 符号描述例子-减法3 - 2=1+加法3 + 2=5*乘法3 * 2=6/除法4 / 2=2%取模 取余数3 % 2=1**幂2 ** 3=8//取...

3988
来自专栏柠檬先生

JavaScript 基础(六) 数组方法 闭包

在一个对象中绑定函数,称为这个对象的方法。 在JavaScript 中,对象的定义是这样的;     var guagua = {         na...

23410
来自专栏刘望舒

算法(二)初等排序前篇[插入和冒泡排序]

前言 排序是算法的基础,排序有很多种方法,有些方法实现起来很简单,但是效率较差,我们可以将这些排序的方法称之为初等排序。这篇文章我们就来学习初等排序中的插入排序...

1749

扫码关注云+社区