单向链表上的快速排序

链表是许多算法和应用程序中常用的数据结构。与静态数组不同，它们允许高效地插入和删除元素。然而，与普通数组相比，高效地对链表进行排序带来了独特的挑战。快速排序是数组中最受欢迎的排序算法之一，以其快速的平均性能而闻名。本文将讨论如何将快速排序改编为以 O(n log n) 的时间复杂度对单链表进行排序。

高效地对链表进行排序对于许多用例都很重要。虽然 C 等语言提供了用于排序数组的 Qsort 库函数，但链表需要自定义排序方法。快速排序是排序数组的最佳算法，但在链表上实现需要进行一些修改。我们将通过一个分步指南来介绍如何将快速排序算法应用于原地排序单链表。我们将涵盖诸如选择枢轴、围绕枢轴进行分区、递归排序子列表以及将已排序的子列表连接起来等细节。通过正确的枢轴选择和分区过程中的注意事项，快速排序即使对于链表也能实现其 O(n log n) 的快速平均情况运行时间。

什么是快速排序？

快速排序是一种分治排序算法，它选择数组中的一个“枢轴”元素，并将其他元素根据它们小于或大于枢轴的值分区到两个子数组中。

快速排序的关键步骤是

选择枢轴

选择枢轴很重要，因为它会影响分区和运行时间。一些常见的枢轴选择方法

• 第一个元素 - 简单，但在已排序的数组上可能导致最坏情况 O(n^2)。
• 最后一个元素很简单，但存在与上述相同的问题。
• 第一个、中间和最后一个元素的中位数 - 增加了 O(n) 的成本，但提高了平衡分区的几率。
• 随机元素 - 很好地保证了 O(n log n) 的运行时间。需要随机数生成器。

围绕枢轴进行分区

它是快速排序的核心步骤。它重新排列枢轴索引周围的元素。典型的分区例程

• 将左 (l) 和右 (r) 索引变量初始化为开始和结束。
• 循环直到 l 仍然小于 r
• 增加 l 直到找到一个大于枢轴的元素。
• 减少 r 直到找到一个小于枢轴的元素。
• 如果 l 仍然小于或等于 r，则交换索引 l 和 r 处的元素。
• 最后，将枢轴与索引 r 处的元素交换。

它将数组分为 0 到 r-1 的小于枢轴的元素、r 处的枢轴以及 r+1 到末尾的大于枢轴的元素。

递归排序

每次分区调用时，算法都会在较小的子集上递归操作

• 对从索引 0 到 r-1 的左子集递归调用快速排序。
• 对从 r+1 到末尾的右子集递归调用快速排序。

基本情况是空或单元素子集，不需要排序。

递归树的深度为 O(log n)。

时间和空间复杂度

• 时间复杂度：平均情况 O(n log n)。最坏情况 O(n^2)。
• 空间复杂度：递归调用的栈空间为 O(log n)。

优化

一些可以提高性能的优化

• 对于小数组，切换到插入排序。
• 选择一个随机枢轴以避免最坏情况。
• 尾部调用消除或迭代而不是递归。

快速排序的属性

以下是快速排序算法的一些关键属性和特征

• 基于比较的排序 - 快速排序会比较元素并将它们根据比较结果交换到相应的位置。这使得它能够处理任何可比较的数据类型。
• 分治法 - 快速排序采用分治法将问题分解为更小的子问题。这种递归分解是其效率的关键。
• O(n log n) 时间复杂度 - 快速排序的平均运行时间为 O(n log n)。这对于基于比较的排序来说是最优的。它比插入排序和合并排序等算法更快。
• O(n^2) 最坏情况 - 在最坏情况下，当枢轴导致非常不平衡的分区时，快速排序的性能会下降到 O(n^2) 时间。这种情况很少见，可以通过随机选择枢轴来避免。
• 缓存友好 - 快速排序在操作相邻分区的数据子集时表现出良好的局部性。它能很好地利用快速缓存内存。
• 原地排序 - 快速排序是原地排序，只需要一个小的辅助栈用于递归。在操作元素时不需要额外的存储空间。
• 不稳定排序 - 作为一种原地排序，快速排序不会保留相等元素的相对顺序。这使得它不适用于某些应用。
• 非自适应 - 即使数组已部分排序，快速排序也会始终将问题分解为基本情况。像合并排序这样的自适应算法能更好地处理这些情况。
• 难以并行化 - 快速排序的递归性质和对枢轴的依赖性使其难以在多个 CPU 核心上高效地并行化。

因此，总而言之，快速排序在排序方面提供了快速的平均性能，同时有效地利用了内存缓存。但是，在各种用例中必须考虑其不稳定性以及缺乏自适应性。

使用快速排序的优点

速度

• 快速排序的平均时间复杂度为 O(n log n)，这是最优的。这使其比插入排序、选择排序、冒泡排序等具有二次时间复杂度的算法更快。
• 它也比堆排序和合并排序更快，后者具有 O(n log n) 的最坏情况时间，但常数因子在实践中会减慢它们的速度。快速排序利用分区来实现更快的实际性能。

内存使用

• 快速排序是原地排序，只需要 O(log n) 的递归空间。像合并排序这样的算法需要 O(n) 的额外空间来复制数据。
• 通过操作组织成分区的数据，它具有更好的缓存性能。这最大限度地减少了缓慢的内存访问。

简单性

• 与需要维护额外数组/列表的合并排序相比，快速排序的实现更简单。
• 具有单个循环和交换的原地分区例程易于编码。
• 它是优雅的分治递归算法的一个典型示例。

通用性

• 与依赖于键的基数排序不同，它可以用于所有可比较的数据类型。
• 不限于数字。可以对字符串、结构、自定义对象等进行排序。

适应性

• 各种优化，如枢轴选择、原地分区等，允许快速排序适应不同情况。
• 如果需要保留元素顺序，可以对其进行修改以实现稳定行为。

因此，总而言之，快速排序的最高速度、高效的内存使用、简单的实现和适应性使其在广泛的用例中相对于其他排序算法具有显著优势。

Python 实现单链表上的快速排序

输出

说明

1. Node 类代表每个节点，包含数据和下一个指针。
2. partition(head, tail) 处理围绕枢轴对列表进行分区
   • 检查空列表或单个节点。如果是这种情况，则返回 head。
   • 选择第一个节点 (head) 作为枢轴元素。
   • 将 left 和 right 标记初始化为 head 和 head.next。
   • 循环遍历列表直到 right != tail.next
     • 如果 right.data 小于枢轴，则将 right.data 与 left.data 交换，以将其放在枢轴之前。
     • 前进 left 和 right 指针。
   • 最后，将枢轴与 left 标记处的值交换。
   • 返回 left 索引，它将列表分成较低和较高的分区。
3. quickSort(head, tail) 递归地对列表进行排序
   • 基本情况 - 空列表或单节点列表。
   • 调用 partition() 将列表分成两部分。
   • 对从 start 到 partition 返回的枢轴索引的左分区递归调用 quickSort。
   • 对从 pivot.next 到 end 的右分区递归调用 quickSort。
4. printList() 打印链表数据。
5. main 部分创建一个链表，对整个列表调用 quickSort，并打印排序后的结果。

因此，总而言之，它围绕枢轴原地对列表进行分区，递归地对子列表进行排序，并迭代此过程以对整个列表进行排序。关键方面是如何在没有额外空间的情况下进行有效分区。

结论

在本文中，我们探讨了实现快速排序算法以在平均 O(n log n) 时间内高效地对单链表进行排序。关键思想包括选择一个好的枢轴，通过重新排列节点指针围绕枢轴对列表进行分区，以及在子列表上应用分治递归。通过适当的枢轴方案和仔细的列表操作，快速排序应用于链表时可以与其在数组上的出色性能相媲美。它允许在没有数据移动或额外存储开销的情况下进行排序。链表上的快速排序展示了该算法在不同数据结构上的灵活性。