五分钟学会一个很有用的排序:归并排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

你可以关注公众号 五分钟学算法 获取更多排序内容。

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

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  • 自下而上的迭代;

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

来源:https://github.com/hustcc/JS-Sorting-Algorithm

算法演示

image

排序动画过程解释

  1. 首先,将数字分割成两片区域
  2. 将数字分割成两片区域
  3. 。。。。。。
  4. 直到每片区域只有一个元素
  5. 分割完成
  6. 接下来,将分割的每片区域进行合并组合
  7. 合并时,按照数字的升序移动,使得合并后的数字在组内按升序排列
  8. 当合并包含多个数字的组时,比较开头的数字,移动其中较小的数字
  9. 比如在动画中,比较开头的 4 和 3
  10. 其中 4 大于 3, 因此移动 3
  11. 按照同样的逻辑去比较该列剩余的头数
  12. 4 小于 7 ,所以移动 4
  13. 。。。。。。
  14. 递归的重复组的合并操作,直到所有数字都在一个组中。
  15. 完成 归并排序 啦~

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

C++代码实现

C++代码实现

Java代码实现

Java代码实现

Python代码实现

Python代码实现

JavaScript代码实现

JavaScript代码实现

如果你是iOS开发者,可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

你可以关注公众号 五分钟学算法 获取更多排序内容。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

洛谷 P1019 单词接龙【经典DFS,温习搜索】

P1019 单词接龙 题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”...

3796
来自专栏伪君子的梦呓

leetcode 题解~两数之和 ~ C++做法

1745
来自专栏数据结构与算法

26:统计满足条件的4位数个数

26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数,求出其中满足以下条件的数的个数:  个位数上的...

4304
来自专栏用户画像

7.6.2 内部排序算法的应用

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序...

701
来自专栏大闲人柴毛毛

剑指 offer——面试题8求旋转数组的最小值

题目:将一个非递减序列的某一处切一刀,再把前半段序列放到后半段序列的后面,这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。 这本质上是一个求最值...

3406
来自专栏赵俊的Java专栏

奇偶分割数组

1564
来自专栏python读书笔记

《python算法教程》Day9 - 快速排序法快速排序法简介代码展示

这是《python算法教程》第9篇读书笔记,笔记的主要内容为快速排序法。 快速排序法简介 快速排序法运用分治法的方式,将需要排序的序列细分成小序列进行排序。 ...

38710
来自专栏小小挖掘机

Numpy基础知识点汇总

1、概述 Numpy是高性能科学计算和数据分析的基础包,它的部分功能如下: 1)ndarray,一个具有矢量算术运算和复杂广播能力的快速且节省空间的多维数组。 ...

3114
来自专栏技术杂谈

给出一组非负整数,重新排序组成最大的数

先把对比的数字转成字符,拼接后再转成整数进行大小对比,即 int(a+b) 与 int(b+a) 进行降序排列。代码1。

6038
来自专栏Petrichor的专栏

numpy: np.where

Note : 不接受 list 型的参数,只接受 `ndarray 型输入。

1163

扫码关注云+社区

领取腾讯云代金券