单向链表归并排序（单向链表归并排序怎么排）



主要目的是将两个已排序的序列合并成一个有序的序列。

整个算法的执行过程用mergeSort(a[ ], l, r)描述，代表当前待排序数组a，左区间下标l，右区间下标r，分以下步骤。

1、计算中点 mid = （1 + r）/2。

2、 递归调用mergeSort(a[ ], l, mid) 和 mergeSort(a[ ], mid+1, r)。

3、将第2步中两个有序的数组合并，再存储到 a[ll:r]中。

调用时，调用mergeSort(a[ ], 0, n-1)就能得到整个数组的排序结果了

时间复杂度：

归并排序对应的数据结构是一棵二叉树，对于两个大小为n1,n2的排序数组A和B，我们可以在O(n)时间内进行排序，归并排序调用的次数就是二叉树的高度log2n， 所以归并排序的时间复杂度为O(nlog2n)。 

空间复杂度：

归并排序在归并过程中需要一个额外的一个 辅助数组 ，并且最大长度为原数组的长度，所以空间复杂度为O(n)。

优点：

1、稳定，相同元素的相对顺序保持不变

2、可扩展，归并算法可以很容易地扩展到并行运算中，通过并行来提高排序效率。

缺点：

1、需要额外的空间，可能内存受限。

2、复杂，归并算法的实现相对复杂，代码量相对较长。

实现用一个和给定元素个数一样大的数组，作为函数传进去，所有 辅助数组能干的事情，都可以在这个传参进去的数组上进行操作，这样就免去了内存的频繁的申请和释放。

mergeSort函数实现了归并排序的核心逻辑，通过递归地将数组分割成子数组，然后调用merge函数进行合并。  merge函数负责将两个已排序的子数组合并成一个有序的数组。

在归并排序的合并过程中，有两种情况会出现剩余的未合并元素：

1. 左子数组元素先处理完

• 例如，左子数组为[1, 3, 5]，右子数组为[4, 6, 8]。在合并过程中，会比较两个子数组的第一个元素，即1和4，将1放入原始数组。接着比较3和4，将3放入原始数组，再比较5和4，将4放入原始数组。此时左子数组的元素已经全部处理完，但右子数组还有[6, 8]未处理。

2. 右子数组元素先处理完

• 假设左子数组为[2, 4, 6]，右子数组为[1, 3]。在合并时，先比较2和1，将1放入原始数组，接着比较2和3，将2放入原始数组，再比较4和3，将3放入原始数组。这时右子数组的元素全部处理完，而左子数组还有[4, 6]未合并。

这两种情况都会导致有剩余的未合并元素，所以需要额外的循环来处理这些剩余元素，以确保所有元素都能正确地合并到原始数组中。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/43712.html