【图解数据结构】 一组动画彻底理解归并排序
source link: https://www.cxyxiaowu.com/2176.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【图解数据结构】 一组动画彻底理解归并排序
由于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 获取更直观可调试运行的源码。
如果你想获取高清的动画演示，在 五分钟学算法 公众号里回复 归并排序 即可。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK