由于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 获取更直观可调试运行的源码。

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


大家都在看

【图解数据结构】一组动画演示冒泡排序

【图解数据结构】一组动画彻底理解二叉树遍历


【图解数据结构】 一组动画彻底理解归并排序


五分钟学算法

【图解数据结构】 一组动画彻底理解归并排序
【图解数据结构】 一组动画彻底理解归并排序

长按识别二维码关注:为您提供更多算法动画解析