文章目录[x]
- 1:归并排序
- 2:算法步骤
- 3:算法演示
- 4:排序动画过程解释
归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
- 自下而上的迭代；
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
来源：https://github.com/hustcc/JS-Sorting-Algorithm
算法演示
动画演示加载有点慢，请稍等片刻
排序动画过程解释
- 首先，将数字分割成两片区域
- 再将数字分割成两片区域
- 依次划分
- 直到每片区域只有一个元素
- 分割完成
- 接下来，将分割的每片区域进行合并组合
- 合并时，按照数字的升序移动，使得合并后的数字在组内按升序排列
- 当合并包含多个数字的组时，比较开头的数字，移动其中较小的数字
- 比如在动画中，比较开头的 4 和 3
- 其中 4 大于 3， 因此移动 3
- 按照同样的逻辑去比较该列剩余的头数
- 4 小于 7 ，所以移动 4
- 同样的逻辑去进行接下来的操作
- 递归的重复组的合并操作，直到所有数字都在一个组中。
- 完成 归并排序
转载自：https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247483936&idx=1&sn=c2200cfc66dab87070307badd78beb7a&chksm=fa0e6da1cd79e4b71ab92d6f57713bef20857bdcf185f980155bc4e499ba4d0678b921813819&scene=21#wechat_redirect