对C中的链表进行排序

Question

我被要求编写一个函数，其中包含3个未排序的链接列表，并返回一个包含所有三个列表的单一排序链表。什么是你能想到的最好的方式？

我没有真正限制内存，但是如果使用/不使用内存限制，你会怎么做？

Answer 1

链表没有有效的排序算法。 进行数组，排序和重新链接。

Answer 2

如果3个列表单独排序，问题会很简单，但因为它们不是更棘手。

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

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

将列表转换为数组可能会使得事情在能够使用更高级的排序技术方面更高效一些，但转换为数组的成本必须考虑并与原始列表的大小相平衡。

Answer 3

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

与大多数O（n log n）排序算法不同，合并排序可以高效地在链接列表上运行。在一个高层次的，直觉的背后归并排序一个链表如下：

1. 作为基础的情况下，如果列表中零个或一个元素，它已经被排序。
2. 否则：
   1. 拆分列表分成大致相等大小的两个列表，可能通过移动奇数元素到一个列表和偶数元素到另一个。
   2. 递归使用合并排序对这些列表进行排序。
   3. 应用merge步骤将这些列表组合到一个排序列表中。

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

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，但也知道如果随机选择一个枢轴元素，则运行时的概率为O（n log n） 。在一个数组中，这很容易（只需选择一个随机数组索引），但是在链表中更复杂。最简单的方法是从0到列表长度之间选择一个随机数，然后在O（n）时间内选择该列表的元素。或者，有一些非常酷的方法可以从链表中随机选取一个元素;这里描述了one such algorithm。

---

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

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

1. 初始化一个空链表持有的结果。
2. 对于每3名连接的列表：
   1. 虽然这个链表不是空的：在整个结果列表
      1. 扫描，找到位置，其中这个链表的第一个元素所属。
      2. 在该位置插入元素。

---

另一个为O（n 2 ）排序算法可以适于链表是selection sort。这可以通过使用该算法非常容易地实现（假设您有一个双向链表）：

1. 初始化一个包含结果的空列表。
2. 虽然输入列表不为空：
   1. 扫描链表寻找最小的剩余元素。
   2. 从链接列表中删除该元素。
   3. 将该元素追加到结果列表中。

这为O也运行（N ）时间和仅使用O（1）的空间，但在实践中它比插入排序慢;尤其是它总是运行在Θ（n ）时间。

---

根据链接列表的结构，你可能会得到一些非常棒的黑客。特别是，如果您给予加倍链接列表，则每个链接列表单元格中有两个指针空间。鉴于此，您可以重新解释这些指针的含义，做一些相当荒谬的排序技巧。

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

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

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

您也可以考虑以这种方式实施heap sort，虽然这有点棘手。

---

希望这有助于！

Answer 4

我在想你可以应用快速排序。它与合并排序几乎相同，唯一不同的是你首先分割然后合并，在这里你首先“合并”然后你分割。如果你看看有点不同的是，归并快速排序方向相反

归并：

分裂 - >递归 - >合并

快速排序：

umnerge（合并对面） - >递归 - >加入（与split相反）

Answer 5

@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。