c - 在 C 中对链表进行排序

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

7年前关闭。




Improve this question




我被要求编写一个函数，该函数接受 3 个未排序的链表并返回一个组合了所有三个列表的单个排序链表。你能想到的最好方法是什么？

我真的没有内存限制，但是有/没有内存限制你会怎么做？

Answer 1

一种选择是使用 merge sort在所有三个链表上，然后使用最后一个合并步骤将它们合并到一个整体排序列表中。

与大多数 O(n log n) 排序算法不同，归并排序可以在链表上高效运行。在高层次上，链表上的归并排序背后的直觉如下:

作为基本情况，如果列表有零个或一个元素，则它已经排序。

除此以外:

将列表分成大小大致相等的两个列表，可能是将奇数元素移动到一个列表中，将偶数元素移动到另一个列表中。

递归地使用归并排序对这些列表进行排序。

申请 merge将这些列表合并为一个排序列表的步骤。

链表上的合并算法真的很漂亮。伪代码的工作原理大致如下:

初始化一个包含结果的空链表。

只要两个列表都不为空:

如果第一个列表的第一个元素小于第二个列表的第一个元素，则将其移到结果列表的后面。

否则，将第二个列表的第一个元素移到结果列表的后面。

现在正好有一个列表是空的，将第二个列表中的所有元素移动到结果列表的后面。

这可以在 O(n) 时间内运行，因此归并排序的整体复杂度为 O(n log n)。

对所有三个列表进行独立排序后，您可以应用合并算法将三个列表合并为一个最终排序列表。或者，您可以考虑将所有三个链表连接在一起，然后使用巨大的合并排序过程同时对所有列表进行排序。没有明确的“正确方法”可以做到这一点；这真的取决于你。

上述算法在 Θ(n log n) 时间内运行。它还仅使用 Θ(log n) 内存，因为它不分配新的链表单元，并且只需要每个堆栈帧中的空间来存储指向各种列表的指针。由于递归深度为 Θ(log n)，因此内存使用量也是 Θ(log n)。

另一个可以在链表上实现的 O(n log n) 排序是对 quicksort 的修改。 .尽管快速排序的链表版本速度很快(预计仍为 O(n log n))，但由于缺乏连续存储数组元素的局部性影响，因此它不如适用于数组的就地版本快.然而，当应用于列表时，它是一个非常漂亮的算法。

快速排序背后的直觉如下:

如果您有一个零元素或一个元素列表，则该列表已排序。

除此以外:

选择列表中的某个元素用作枢轴。

将列表分成三组 - 小于枢轴的元素、等于枢轴的元素和大于枢轴的元素。

递归排序较小和较大的元素。

将三个列表连接为更小，然后相等，然后更大以获取整体排序列表。

快速排序的链表版本的优点之一是分区步骤比数组情况要容易得多。选择一个主元后(稍后详细介绍)，您可以通过为小于、等于和大于列表创建三个空列表来执行分区步骤，然后对原始链接进行线性扫描列表。然后，您可以将每个链表节点附加/预先添加到与原始存储桶对应的链表。

使这项工作发挥作用的一个挑战是选择一个好的枢轴元素。众所周知，如果主元的选择不好，快速排序可以退化到 O(n2) 时间，但也知道如果你随机选择一个主元元素，运行时间很可能是 O(n log n)。在数组中这很容易(只需选择一个随机数组索引)，但在链表情况下则更棘手。最简单的方法是在 0 和列表长度之间选择一个随机数，然后在 O(n) 时间内选择列表中的那个元素。或者，有一些非常酷的方法可以从链表中随机选择一个元素； one such algorithm描述在这里。

如果你想要一个只需要 O(1) 空间的更简单的算法，你也可以考虑使用 insertion sort对链表进行排序。虽然插入排序更容易实现，但它在最坏情况下的运行时间为 O(n2)(尽管它也有 O(n) 最佳情况)，因此除非您特别想避免合并排序，否则它可能不是一个好的选择.

插入排序算法背后的思想如下:

初始化一个包含结果的空链表。

对于三个链表中的每一个:

虽然该链表不为空:

扫描结果列表以找到此链表的第一个元素所属的位置。

在该位置插入元素。

另一种适用于链表的 O(n2) 排序算法是 selection sort .使用这个算法可以很容易地实现(假设你有一个双向链表):

初始化一个包含结果的空列表。

虽然输入列表不为空:

扫描链表寻找最小的剩余元素。

从链表中删除该元素。

将该元素附加到结果列表中。

这也在 O(n2) 时间内运行并且仅使用 O(1) 空间，但实际上它比插入排序慢；特别是，它总是在 Θ(n2) 时间内运行。

根据链接列表的结构方式，您可能能够逃脱一些非常棒的黑客攻击。特别是，如果您收到 加倍 -链表，那么每个链表单元格中有两个指针的空间。鉴于此，您可以重新解释这些指针的含义以执行一些非常荒谬的排序技巧。

作为一个简单的例子，让我们看看如何实现 tree sort使用链表单元格。思路如下。当链表单元格存储在链表中时，next 和 previous 指针具有其原始含义。然而，我们的目标是迭代地将链表单元从链表中拉出，然后将它们重新解释为二叉搜索树中的节点 a，其中下一个指针表示“右子树”，前一个指针表示“左子树”。如果你被允许这样做，这里有一个非常酷的实现树排序的方法:

创建一个指向链表单元格的新指针，该单元格将用作指向树根的指针。

对于双向链表的每个元素:

从链接列表中删除该单元格。

将该单元视为 BST 节点，将该节点插入到二叉搜索树中。

按顺序走 BST。每当您访问一个节点时，将其从 BST 中删除并将其插入回双向链表中。

这在最佳情况下运行 O(n log n) 时间和最坏情况下运行时间为 O(n2)。在内存使用方面，前两步只需要 O(1) 内存，因为我们正在从旧指针中回收空间。最后一步也可以使用一些特别聪明的算法在 O(1) 空间中完成。

您也可以考虑实现 heap sort这种方式也是如此，虽然它有点棘手。

希望这可以帮助!