归并排序本质就是一种思想，在很多题目都可以用到
一、归并排序的原理
归并排序（MergeSort） 是建立在归并操作上的一种有效的排序算法，采用分治法排序，分为分解、合并两个步骤。
分解：将数组分割成两个数组，再分别将两个数组又细分成2个数组，直到，最后每个数组都是一个元素，这时将该单元素数组看为有序数组
合并：将分割的有序数组进行排序，排成有序数组后继续为上一个分割它的数组合并，直到数组被合并成原来的数组，此时已经排好序了
二、递归实现
当左右区间有序时，就可以开始归并排序
因此需要先 递归分治，将区间像之前的方法一直分解
🐻为什么要开临时数组？
因为在原数组中直接进行排序非常困难，很容易混乱，为了有条理，可以开临时数组临时处理，之后再拷贝回原数组
🐻归并排序—–单趟的思路
左右区间有序时，从每个区间的首个元素开始，一一比较，将较小的优先放进临时数组中，归并排序完成后，再将临时数组中的数据拷贝回到原数组
🐻归并排序—–整体逻辑
观察动图：递归分割区间至一个数值后，就会开始合并，进行归并排序
由上述过程得出的归并排序的总代码：
三、非递归实现
不能像上一章节中讲解的快速排序非递归写法，直接用 栈模拟
快排本质是一种 前序遍历，就可以直接用栈模拟：先对当前区间进行一次快排，再分解左右区间时入栈，顺序就是 根节点->左节点->右节点（这里前序遍历的思想属于 二叉树章节）
而 归并排序本质是 后序遍历，是一直分解到最小左右区间后，再执行归并排序，就是 先访问左右节点，最后再到 根节点，顺序是： 左节点->右节点->根节点
不能用栈模拟，而是用 循环
🐻先理解 递归版本的过程思想：
- 在使用 递归 进行归并排序时，我们分析了 函数 递归到最后 时，两个需要归并的数组中每个区间里面只有一个元素，所以直接比较两个元素大小，然后再添加到 tmp 数组中，再将 tmp 数组相应区间元素拷贝进 原数组 a
- 然后再返回上一层函数中，此时该层函数中 两个需要归并的区间中每个区间里面有 两个 元素，并且这两个区间 已经有序，所以直接 对这两个区间进行归并排序
- 依次类推上去，直到回到第一次调用函数
- 此时数组 arr 中左边的数组区间 有序，右边的数组区间 也有序，此时将左右两个数组区间 进行归并，将归并排序结果放进 tmp 数组，再将tmp中的内容拷贝到arr，arr也变为有序数组了。
🐻再理解 循环实现的 非递归版本：
- gap 代表 单个区间元素个数，也就是 区间长度
- 一次 归并排序 两个 长度为 gap 的区间
- 若想要排序下一组（即两个 长度为 gap 的区间），就需要每轮的最后，一次跳过 2*gap 长度（代表跳过前面排序的 两个 长度为 gap 的区间）
- 从1开始对 两个有序数组 进行排序，直到 gap >= n 时结束 ( n 为数组长度，这个就是外层while循环的结束条件 )
🦐演示过程
🦐利用 循环 实现归并排序时，我们也可以 先将数组中每一个元素 单独作为一组
🦐 第一轮 gap == 1 时：让 两两元素 归并排序 为一个含有两个元素的有序数组，然后 gap *= 2（gap 变成了 2）
🦐第二轮 gap == 2 时：让 两个含有两个元素的有序数组 归并 为一个含有四个元素的有序数组，然后 gap *= 2（gap 变成了 4）
🦐第三轮 gap == 3 时：然后再让 两个含有四个元素的有序数组归并为一个含有八个元素的有序数组，然后 gap *= 2（gap 变成了 8）
🦐就这样一直循环下去，直到 gap >= n ( n 为数组长度，这个就是外层while循环的结束条件 ) 时结束，结束时，数组就有序了
🦐演示 单趟的逻辑
演示代码书写逻辑
以 gap == 1 和 gap == 2 举例
可以发现规律，区间 右边界 和 gap 有关：
自己带入下标算一下就知道了
🦐举例演示 单趟的逻辑：以 gap == 1 为例
🦐演示 整体的逻辑
思路：
由上面的分析可知，gap 是不断变化的，且每轮都要循环遍历全部区间
因此，需要使用
外层一个while 循环 gap
内层一个 for：循环每组的起点，为了遍历到全部组别
整体逻辑的 初步代码如下
🦐数组越界问题
但是要注意一点，gap每轮乘 2，而归并排序要求每个区间长度都必须等于 gap ，因此需要数组的全部元素个数 刚好是 2的次方倍，区间才能以 长度为 gap ，进行平均分割，才不会出现越界的问题；
否则，上面这段代码就会出现越界情况
打印观察每个 gap 对应处理的区间
可以发现，数组 若一共 9 个元素，下标最多到 8 ，下面的打印运行过程中的区间数据，却出现了 严重的越界情况，就是因为 9 不是 2的次方倍，则肯定会越界
在这个代码下，只有 begin1 不可能越界，其他的都有可能越界，那么怎么处理边界问题呢？
🦐越界有三种情况
第一种：第一个区间的 end1 越界
则这一小区间就无需执行 本轮的归并排序了（不是以后都不归并，而是当前这一轮不用了），保留原数组数据即可（因为一个区间肯定保证是有序的）
第二种： 第二个区间的begin2 越界
说明第二个区间也不存在，则这一小区间也无需执行 本轮的归并排序了，保留原数组数据
第三种： 第二个区间的 end2 越界
当 end2 越界，（这里也就说明前面几项都没越界），需要修正end2：end2 直接等于右边界 end2 = R （因为越界的一定是最后一组）
则中间加一个判断
同时 memcpy 也需要调整，即拷贝个数不一定是 2*gap 了
🐻 非递归实现的 总代码
四、时间复杂度
从图中可以思考：归并排序的递归展开图是一棵满二叉树或完全二叉树，一共最多有 logN 层，每一个需要 归并排序共 N 次，则总共需要 NlogN 次，即 归并排序的时间复杂度为 O(NlogN)
五、性能对比
声明：下面我用代码随机生成 个数据，执行几个排序算法，显示的数据为 时间，以 ms 为单位
发现两者差异不大
快排和归并排序时间复杂度都是 O(nlogn) 的，但理论上 快排更快
🫡至此，第四章完结！
到此这篇单向链表归并排序（单向链表归并排序方法）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！【若文章有什么错误或则可以改进的地方，非常欢迎评论区讨论或私信指出】
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/24783.html