【图解数据结构】 归并排序

栏目: 数据库 · 发布时间: 5年前

内容简介:由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

前言

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

归并排序

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

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

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

  • 自下而上的迭代;

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

算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  4. 重复步骤 3 直到某一指针达到序列尾;

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

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

算法演示

【图解数据结构】 归并排序

排序动画过程解释

  1. 首先,将数字分割成两片区域

  2. 将数字分割成两片区域

  3. 。。。。。。

  4. 直到每片区域只有一个元素

  5. 分割完成

  6. 接下来,将分割的每片区域进行合并组合

  7. 合并时,按照数字的升序移动,使得合并后的数字在组内按升序排列

  8. 当合并包含多个数字的组时,比较开头的数字,移动其中较小的数字

  9. 比如在动画中,比较开头的 4 和 3

  10. 其中 4 大于 3, 因此移动 3

  11. 按照同样的逻辑去比较该列剩余的头数

  12. 4 小于 7 ,所以移动 4

  13. 。。。。。。

  14. 递归的重复组的合并操作,直到所有数字都在一个组中。

  15. 完成 归并排序 啦~

代码实现

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

C++代码实现

【图解数据结构】 归并排序

Java代码实现

【图解数据结构】 归并排序

Python代码实现

【图解数据结构】 归并排序

JavaScript代码实现

【图解数据结构】 归并排序 如果你是iOS开发者,可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

如果你想获取高清的动画演示,在 五分钟学算法 公众号里回复  选择排序 即可。


以上所述就是小编给大家介绍的《【图解数据结构】 归并排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Sovereign Individual

The Sovereign Individual

James Dale Davidson、William Rees-Mogg / Free Press / 1999-08-26 / USD 16.00

Two renowned investment advisors and authors of the bestseller The Great Reckoning bring to light both currents of disaster and the potential for prosperity and renewal in the face of radical changes ......一起来看看 《The Sovereign Individual》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具