内容简介:由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
前言
由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画来描述常见的数据结构和算法。本系列包括十大 排序 、堆、队列、树、并查集、图等等大概几十篇。
归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
-
自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
-
自下而上的迭代;
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
-
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
-
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
-
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
-
重复步骤 3 直到某一指针达到序列尾;
-
将另一序列剩下的所有元素直接复制到合并序列尾。
来源: https://github.com/hustcc/JS-Sorting-Algorithm
算法演示
排序动画过程解释
-
首先,将数字分割成两片区域
-
将数字分割成两片区域
-
。。。。。。
-
直到每片区域只有一个元素
-
分割完成
-
接下来,将分割的每片区域进行合并组合
-
合并时,按照数字的升序移动,使得合并后的数字在组内按升序排列
-
当合并包含多个数字的组时,比较开头的数字,移动其中较小的数字
-
比如在动画中,比较开头的 4 和 3
-
其中 4 大于 3, 因此移动 3
-
按照同样的逻辑去比较该列剩余的头数
-
4 小于 7 ,所以移动 4
-
。。。。。。
-
递归的重复组的合并操作,直到所有数字都在一个组中。
-
完成 归并排序 啦~
代码实现
为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。
C++代码实现
Java代码实现
Python代码实现
JavaScript代码实现
如果你是iOS开发者,可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。
如果你想获取高清的动画演示,在 五分钟学算法 公众号里回复 选择排序 即可。
以上所述就是小编给大家介绍的《【图解数据结构】 归并排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 数据结构与算法:归并排序
- 【 python 学习笔记 -- 数据结构与算法 】归并排序 Merge Sort
- MergeSort归并排序和利用归并排序计算出数组中的逆序对
- 归并排序求逆序数
- 算法 | 归并排序
- 死磕归并排序算法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
内容创业:内容、分发、赢利新模式
张贵泉、张洵瑒 / 电子工业出版社 / 2018-6 / 49
越来越多的内容平台、行业巨头、资本纷纷加入内容分发的战争中,竞争非常激烈。优质的原创性内容将成为行业中最宝贵的资源。在这样的行业形势下,如何把内容创业做好?如何提高自身竞争力?如何在这场战争中武装自己?是每一位内容创业者都应该认真考虑的问题。 《内容创业:内容、分发、赢利新模式》旨在帮助内容创业者解决这些问题,为想要进入内容行业的创业者出谋划策,手把手教大家如何更好地进行内容创业,获得更高的......一起来看看 《内容创业:内容、分发、赢利新模式》 这本书的介绍吧!