在C中排序链表[关闭]

问题描述 投票:6回答:5

我被要求编写一个函数,它接受3个未排序的链表并返回一个组合所有三个列表的单个排序链表。您能想到的最佳方式是什么?

我真的没有内存限制,但是你有/没有内存限制你会做什么?

c algorithm sorting data-structures linked-list
5个回答
38
投票

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

与大多数O(n log n)排序算法不同,合并排序可以在链表上高效运行。在高级别,链接列表上合并排序背后的直觉如下:

  1. 作为基本情况,如果列表包含零个或一个元素,则它已经排序。
  2. 除此以外: 将列表拆分为两个大小相等的列表,可能是将奇数元素移动到一个列表中,将偶数元素移动到另一个列表中。 递归使用合并排序来对这些列表进行排序。 应用merge步骤将这些列表组合成一个排序列表。

链表上的合并算法非常漂亮。伪代码大致类似于:

  1. 初始化保存结果的空链表。
  2. 只要两个列表都不为空: 如果第一个列表的第一个元素小于第二个列表的第一个元素,请将其移动到结果列表的后面。 否则,将第二个列表的第一个元素移动到结果列表的后面。
  3. 现在只有一个列表为空,将所有元素从第二个列表移动到结果列表的后面。

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

一旦您单独对所有三个列表进行了排序,就可以应用合并算法将三个列表组合成一个最终排序列表。或者,您可以考虑将所有三个链接列表连接在一起,然后使用巨型合并排序传递同时对所有列表进行排序。这样做没有明确的“正确方法”;这真的取决于你。

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


您可以在链表上实现的另一种O(n log n)排序是对quicksort的修改。尽管快速排序的链接列表版本很快(仍然是O(n log n)预期),但由于缺少连续存储的数组元素的局部效应,它的速度不如在数组上工作的就地版本快。但是,这是一个应用于列表的非常漂亮的算法。

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

  1. 如果您有零元素或单元素列表,则对列表进行排序。
  2. 除此以外: 选择列表中的某个元素作为数据透视表。 将列表拆分为三组 - 小于枢轴的元素,等于枢轴的元素,以及大于枢轴的元素。 递归地对较小和较大的元素进行排序。 将三个列表连接为较小,然后相等,然后更大以获取整个排序列表。

quicksort的链表版本的一个不错的方面是分区步骤比在数组情况下更容易。在选择了一个数据透视图(稍后详细说明)之后,您可以通过为小于,等于和大于列表创建三个空列表来执行分区步骤,然后对原始链接进行线性扫描名单。然后,您可以将每个链接列表节点附加/前置到与原始存储桶对应的链接列表。

实现这一目标的一个挑战是选择一个好的枢轴元素。众所周知,如果枢轴的选择不好,快速排序可以退化到O(n2)时间,但是众所周知,如果你随机选择一个枢轴元素,运行时很可能是O(n log n)。在数组中这很容易(只是选择一个随机数组索引),但在链表中的情况比较棘手。最简单的方法是在0和列表长度之间选择一个随机数,然后在O(n)时间内选择列表中的那个元素。或者,有一些非常酷的方法可以从链表中随机选取一个元素; one such algorithm在这里描述。


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

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

  1. 初始化保存结果的空链表。
  2. 对于三个链表中的每一个: 虽然该链表不是空的: 扫描结果列表以查找此链接列表的第一个元素所属的位置。 在该位置插入元素。

可以适用于链表的另一种O(n2)排序算法是selection sort。通过使用此算法,可以非常轻松地实现这一点(假设您有一个双向链表):

  1. 初始化保存结果的空列表。
  2. 输入列表不为空: 扫描链表以查找剩余的最小元素。 从链接列表中删除该元素。 将该元素附加到结果列表。

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


根据链接列表的结构,您可能会遇到一些非常棒的黑客攻击。特别是,如果给出双向链表,那么在每个链表单元格中都有两个指针空间。鉴于此,您可以重新解释这些指针的含义,以做一些非常荒谬的排序技巧。

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

  1. 创建一个指向链表单元格的新指针,该指针将用作指向树根的指针。
  2. 对于双向链表的每个元素: 从链接列表中删除该单元格。 将该单元格作为BST节点处理,将该节点插入二叉搜索树。
  3. 做BST的有序步行。每当您访问节点时,将其从BST中删除并将其插回到双向链接列表中。

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

您也可以考虑以这种方式实现heap sort,尽管它有点棘手。


希望这可以帮助!


0
投票

如果3个列表是单独排序的,那么问题就很简单了,但是因为它们不是很棘手。

我会编写一个函数,它将排序列表和未排序列表作为参数,遍历未排序列表的每个项目,并依次将其添加到排序列表中的正确位置,直到未排序列表中没有任何项目。

然后简单地创建一个第四个“空”列表,该列表根据空的本质被“排序”,然后使用每个未排序列表调用您的方法三次。

将列表转换为数组可以使得能够使用更高级的排序技术更有效,但是必须考虑转换为数组的成本并且与原始列表的大小相平衡。


0
投票

我在想你可以快速排序。它与合并排序几乎相同,唯一的区别是你首先拆分然后合并,其中whit快速排序你首先“合并”然后你进行拆分。如果你看起来有点不同,那就是mergesort quicksort在相反的方向

归并排序:

split - > recursion - > merge

快速排序:

umnerge(合并的对面) - >递归 - > join(与split相对)


-1
投票

@templatetypedef在热门帖子中描述的mergesort算法在O(n lg n)中不起作用。因为链表不是随机访问,所以步骤2.1 Split the list into two lists of roughly equal size实际上是指O(n ^ 2 log n)的整体算法来对列表进行排序。试想一下吧。

这是一个使用mergesort对链表进行排序的链接,首先将元素读入数组 - http://www.geekviewpoint.com/java/singly_linked_list/sort


-7
投票

链表没有有效的排序算法。制作数组,排序和重新链接。

© www.soinside.com 2019 - 2024. All rights reserved.