归并排序

作者:柳行刚

编辑:徐 松

基本思想

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

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

相关文章

来自专栏IT可乐

Java数据结构和算法(十三)——哈希表

  Hash表也称散列表,也有直接译作哈希表,Hash表是一种根据关键字值(key - value)而直接进行访问的数据结构。它基于数组,通过把关键字映射到数组...

2578
来自专栏深度学习与计算机视觉

算法-排序算法总结

void print_arr(int array[],int length) { for (int i=0;i<length;i++) { ...

23610
来自专栏架构师小秘圈

秒懂排序算法

作者:郭耀华,来自:cnblogs.com/guoyaohua 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳...

3595
来自专栏用户画像

7.3.1 交换排序之冒泡排序

冒泡排序算法的基本思想是:假设待排序表长为n,从后往前(或从前往后)两两比较相邻元素的值。若为逆序(即A[i-1]>A[i]),则交换它们,直到序列比较完。我们...

652
来自专栏desperate633

[编程题] 双核处理分析代码

一种双核CPU的两个核能够同时的处理任务,现在有n个已知数据量的任务需要交给CPU处理,假设已知CPU的每个核1秒可以处理1kb,每个核同时只能处理一项任务。n...

614
来自专栏desperate633

LeetCode 169. Majority Element题目分析代码

给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。

903
来自专栏desperate633

LintCode 完美平方题目分析代码

给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

612
来自专栏我是东东强

常见算法之排序

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

852
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort) 在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性: ? 上图就是一...

1795
来自专栏武培轩的专栏

排序算法-冒泡排序

算法简介 冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法描述 比较相邻的...

3327

扫码关注云+社区