在C中对链接列表进行排序

Question

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

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

Answer 1

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

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

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

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

1. 初始化保存结果的空链表.
2. 只要两个列表都不为空:
   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. 除此以外:
   1. 选择列表中的某个元素作为数据透视表.
   2. 将列表拆分为三组 - 小于枢轴的元素,等于枢轴的元素,以及大于枢轴的元素.
   3. 递归地对较小和较大的元素进行排序.
   4. 将三个列表连接为较小,然后相等,然后更大以获取整个排序列表.

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

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

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

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

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

另一种可以适用于链表的O(n ²)排序算法是选择排序.通过使用此算法,可以非常轻松地实现(假设您有一个双向链表):

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

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

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

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

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

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

您也可以考虑以这种方式实现堆排序,尽管它有点棘手.

希望这可以帮助!

Answer 2

链表没有有效的排序算法。创建一个数组，排序并重新链接。