单向链表的归并排序

本文介绍了如何在单链表上实现归并排序，包括查找中间节点、递归排序左右子列表以及合并已排序的子列表。分析了时间和空间复杂度。适用于处理链表的工程师。

链表允许高效的插入/删除操作，但在排序时可能会很棘手。归并排序使用分治技术将列表分割成子列表，对子列表进行排序，然后按顺序合并它们。

归并排序

归并排序是一种采用分治策略的算法。它通过将问题分解为子问题，单独解决它们，然后合并结果来解决问题。在对链表进行排序时，归并排序遵循以下步骤：

算法

要将链表分成两部分，可以按照以下步骤操作：

1. 使用两个指针，分别称为慢指针（slow）和快指针（fast），它们都指向链表的头节点。
2. 慢指针一次移动一个节点。快指针一次移动两个节点。
3. 当快指针到达链表末尾时，慢指针将指向中间节点。

接下来，你可以以归并排序的方式递归地对每个子列表进行排序：

1. 对链表的左右两个部分递归地应用归并排序。
2. 递归的基本情况是子列表为空或只有一个节点，这意味着它们已经是有序的。

最后，合并列表：

1. 创建一个节点。设置一个尾指针（tail）来跟踪我们新合并列表的最后一个节点。
2. 使用左指针（left）和右指针（right）遍历每个已排序的子列表。
3. 比较由左指针和右指针指向的节点，并将较小的值插入到合并列表的尾部。
4. 将从中插入值的指针（左指针或右指针）向前移动。
5. 重复此过程，直到其中一个子列表被完全遍历。
6. 一旦我们完成了对一个子列表的遍历，就将另一个子列表中所有剩余的节点追加到我们的合并列表中。

此外，以下是一些可以提高链表上归并排序性能的优化：

1. 在遍历每个子列表以将其插入元素时，始终维护子列表的尾部指针，而不是每次都从头部开始遍历。
2. 在将子列表分成两半（以查找其中点）时，可以预先计算所有节点数，然后除以 2 (n/2) 来获得更平衡的子列表。

可以通过对列表进行自然递归来节省栈空间。

分析

• 时间复杂度 - O(n log n) - 将列表分解成 log n 层，合并每一层需要 O(n) 时间。
• 空间复杂度 - O(n) - 归并排序使用 O(n) 空间来存储已排序的子列表。递归栈使用 O(log n) 空间。

归并排序的优点

效率 - 归并排序 O(n log n) 的时间复杂度使其在大数据集上非常高效。分治策略有助于将问题分解为可以独立解决的小型子问题。

适应性 - 归并排序适用于不同的链表结构，如单向链表、双向链表和循环链表。节点遍历逻辑需要根据链表类型进行调整。

稳定性 - 归并排序是一种稳定的排序算法，这意味着在排序后，具有相同键的元素的原始顺序得以保留。对于具有多个相同键的记录的数据集，此稳定性属性可能很重要。

原地排序 - 归并排序可以在不需要额外的空间来存储列表副本的情况下实现。合并步骤是通过修改链接而不是创建新列表来完成的。

并行性 - 分治法产生的独立子问题可以在并行中解决，从而在多核系统上提高速度。

递归 - 归并排序的递归实现与链表的指针链接结构非常匹配。不需要像数组排序那样进行随机访问。

易于调试 - 归并排序的逐步特性，具有清晰的划分、排序和合并步骤，使得调试比迭代排序技术更简单。

低开销 - 与快速排序等其他算法相比，归并排序的函数调用开销很小，并且只需要最少的索引或额外数据结构。

链表上归并排序的缺点

1. 递归开销 - 对于大型输入，归并排序的递归实现可能导致调用栈产生显著开销，从而导致堆栈溢出错误。迭代式归并排序可以避免此问题。
2. 对于朴素实现不是原地排序 - 合并步骤通常需要创建一个单独的合并列表，暂时将内存使用量加倍。这可以通过原地合并进行优化。
3. 难以并行化 - 归并排序的顺序性和对先前步骤的依赖性使其难以在没有额外协调开销的情况下并行化。
4. 需要链表操作开销 - 与 C/C++ 等语言中的数组索引相比，用于分割和合并列表的指针操作会增加开销。
5. 需要完全遍历链表 - 归并排序始终需要遍历整个链表，如果需要提前终止，对于大型列表来说可能会很慢。
6. 它不缓存友好。 链表具有较差的引用局部性，因此归并排序会损失数组排序能够获得的缓存命中率。
7. 对于小列表，插入排序更快 - 归并排序递归和合并的开销对于排序非常小的列表来说不是最优的，而插入排序通常更快。
8. 难以调整 - 归并排序不像快速排序的枢轴选择或插入排序的提前终止那样容易调整或适应。

因此，总而言之，递归开销、操作成本、局部性差和并行化困难等因素可能使得归并排序的 O(n log n) 在实际应用中不如快速排序等其他排序算法理想。链表结构也消除了链表上归并排序的一些缓存优势。

Python 实现

输出

说明

1. Node 类定义了链表节点，包含数据和下一个指针。
2. mergeSort 函数以链表头节点作为参数。
3. 基本情况 - 如果头节点为 None 或只有一个节点，则已排序。
4. 使用慢指针和快指针技术找到中间节点。
5. 使用 slow.next = None 在中间节点处将列表分成两半。
6. 递归调用 mergeSort 来对左半部分和右半部分进行排序。
7. 调用 merge 函数来合并两个已排序的列表。
8. merge 函数以左侧和右侧已排序的列表作为参数。
9. 创建一个虚拟节点来构建排序列表。将尾部初始化为虚拟节点。
10. 循环直到左指针或右指针为 None
    • 比较左指针和右指针处的数据。
    • 将较小的数据追加到尾部，并更新 tail.next。
    • 将已追加节点的指针向前移动。
    • 将尾部更新为新的最后一个节点。
11. 追加任何非空列表中剩余的节点。
12. 返回 dummy.next，它现在指向排序后的列表头。
13. printList 打印链表。
14. 驱动代码在样本输入上测试 mergeSort。

因此，总而言之，在 Python 中实现链表上的归并排序的关键方面是使用虚拟节点和尾部指针技术来查找中间节点、递归排序子列表以及合并它们。

结论

总而言之，归并排序是一种高效、稳定的排序算法，非常适合链表。通过利用分治方法并递归地将链表分割成更小的已排序子列表，它可以在 O(n log n) 时间内对链表进行排序。合并阶段使用虚拟节点和尾部指针有效地合并已排序的子列表。在链表上实现归并排序需要调整指针操作逻辑，但可以提供快速、原地排序。