我被要求编写一个函数，它接受3个未排序的链表，并返回一个单一的已排序的链表，将所有三个链表组合起来。你能想到最好的方法是什么？
我没有内存限制，但在有/没有内存限制的情况下，你会怎么做？
在C语言中对链表进行排序
6
- Awesomenuts
4
1添加了作业标签。你需要如何排序呢？按字母顺序，从小到大排列吗？ - BlackBear
10将3个列表连接在一起（列表1的尾部->列表2的头部，以此类推），然后您只有一个列表，并且可以使用简单的排序函数进行排序。 - Marc B
你知道哪些排序算法？ - Beta
如果排序需要使用链表排序，则使用一个指向节点的小数组进行自底向上的归并排序是最快的。维基百科示例。由于节点逐个合并到内部数组中，因此可以分别处理这3个列表或将它们连接成单个列表，然后再合并到内部数组中。然后将内部数组合并以形成单个排序列表。 - rcgldr
5个回答
40
一种方法是对这三个链表使用归并排序，然后使用最终的合并步骤将它们合并成一个总体排序的列表。
与大多数O(n log n)排序算法不同，归并排序可以在链表上高效运行。从高层次上讲，链表上归并排序的直觉如下:
1. 作为基本情况，如果列表有零个或一个元素，则已经排序。 2. 否则：
- 将列表分成两个大致相等的列表，可能通过将奇数元素移动到一个列表中，偶数元素移动到另一个列表中。 - 递归使用归并排序来排序这些列表。 - 应用合并步骤将这些列表合并成一个排序列表。
链表上的合并算法真的很美。伪代码大致如下：
1. 初始化一个保存结果的空链接列表。 2. 只要两个列表都不为空：
- 如果第一个列表的第一个元素小于第二个列表的第一个元素，则将其移到结果列表的末尾。 - 否则，将第二个列表的第一个元素移动到结果列表的末尾。
3. 现在只有一个列表为空，将第二个列表中的所有元素移动到结果列表的末尾。
这可以在O(n)时间内运行，因此归并排序的总体复杂度为O(n log n)。
一旦您独立排序了这三个列表，就可以应用合并算法将这三个列表合并为一个最终排序的列表。或者，您可以考虑将所有三个链接列表连接在一起，然后使用巨大的归并排序来同时对所有列表进行排序。没有明确的“正确方法”可供选择；这完全取决于您。
上述算法的运行时间为Θ(n log n)。它还仅使用Θ(log n)的内存，因为它不分配新的链接列表单元，只需要在每个堆栈帧中留出空间来存储指向各个列表的指针。由于递归深度为Θ(log n)，因此内存使用量也为Θ(log n)。
如果您需要一个只需O(1)空间的更简单的算法，您也可以考虑使用插入排序对链表进行排序。尽管插入排序更易于实现，但在最坏情况下它以O(n2)时间运行（尽管它也具有O(n)的最佳情况），因此除非您特别想避免合并排序，否则它可能不是一个好选择。
插入排序算法背后的思想如下：
1. 初始化一个空链表来保存结果。 2. 对于三个链表中的每一个：
- 只要该链表不为空： - 横跨结果列表扫描以找到该链表的第一个元素所属的位置。 - 在该位置插入元素。
根据链表的结构，你可以实现一些非常棒的技巧。特别是，如果你有双向链表，那么每个链表单元格中就有两个指针的空间。在这种情况下，你可以重新解释这些指针的含义，从而实现一些相当荒谬的排序技巧。
作为一个简单的例子，让我们看看如何使用链表单元格来实现tree sort。其想法如下：当链表单元格存储在链表中时，下一个和上一个指针具有它们的原始含义。但是，我们的目标将是迭代地将链表单元格从链表中取出，然后将它们重新解释为二叉搜索树中的节点，其中下一个指针表示“右子树”，上一个指针表示“左子树”。如果你被允许这样做，下面是一种非常酷的实现tree sort的方法：
1.创建一个新的指向链表单元格的指针，它将作为树根的指针。 2.对于双向链表的每个元素： 1）从链表中删除该单元格。 2）将该单元格视为BST节点，将节点插入二叉搜索树中。 3.进行BST的中序遍历。每当你访问一个节点时，将其从BST中删除并重新插入到双向链表中。
与大多数O(n log n)排序算法不同，归并排序可以在链表上高效运行。从高层次上讲，链表上归并排序的直觉如下:
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)），但由于数组元素存储在连续位置上的局部性效应缺失，它并不像作用于数组的原地版本那样快。但是，对于列表来说，这是一个非常美丽的算法。
快速排序背后的直觉如下：
- 如果你有一个零或一个元素的列表，那么该列表已经排序好了。
- 否则：
- 选择列表中的某个元素作为枢轴。
- 将列表分成三组——小于枢轴的元素、等于枢轴的元素和大于枢轴的元素。
- 递归地对较小和较大的元素进行排序。
- 连接三个列表，先是小的，然后是相等的，最后是大的，以得到整体排序的列表。
链表版本的快速排序的一个好处是，分区步骤比数组情况下要容易得多。在选择枢轴之后（稍后会详细介绍），您可以通过为小于、等于和大于列表创建三个空列表，然后在线性扫描原始链表时执行分区步骤。然后，您可以将每个链接列表节点附加/预先附加到对应于原始桶的链接列表。
在使这个算法工作时，最大的挑战是选择一个好的枢轴元素。众所周知，如果选择的枢轴不好，快速排序会退化为O(n^2)时间复杂度，但是如果随机选择枢轴元素，则运行时间具有高概率的O(nlogn)。在数组中，这很容易（只需选择一个随机的数组索引），但在链表情况下则更加棘手。最简单的方法是在0到列表长度之间选择一个随机数，然后在O(n)时间内选择该列表元素。此外，还有一些非常酷的方法可以从链表中随机选择一个元素；其中一个这样的算法在这里描述。如果您需要一个只需O(1)空间的更简单的算法，您也可以考虑使用插入排序对链表进行排序。尽管插入排序更易于实现，但在最坏情况下它以O(n2)时间运行（尽管它也具有O(n)的最佳情况），因此除非您特别想避免合并排序，否则它可能不是一个好选择。
插入排序算法背后的思想如下：
1. 初始化一个空链表来保存结果。 2. 对于三个链表中的每一个：
- 只要该链表不为空： - 横跨结果列表扫描以找到该链表的第一个元素所属的位置。 - 在该位置插入元素。
另一个可用于链表的O(n2)排序算法是选择排序。如果你有一个双向链表，那么可以非常容易地实现这个算法：
- 初始化一个空列表来保存结果。
- 只要输入列表不为空：
- 扫描整个链表，寻找剩余元素中最小的那个。
- 从链表中移除该元素。
- 将该元素添加到结果列表的末尾。
这个算法的时间复杂度也是O(n2)，但它只使用了O(1)的空间，但在实践中它比插入排序要慢；特别地，它总是需要Θ(n2)的时间。
根据链表的结构，你可以实现一些非常棒的技巧。特别是，如果你有双向链表，那么每个链表单元格中就有两个指针的空间。在这种情况下，你可以重新解释这些指针的含义，从而实现一些相当荒谬的排序技巧。
作为一个简单的例子，让我们看看如何使用链表单元格来实现tree sort。其想法如下：当链表单元格存储在链表中时，下一个和上一个指针具有它们的原始含义。但是，我们的目标将是迭代地将链表单元格从链表中取出，然后将它们重新解释为二叉搜索树中的节点，其中下一个指针表示“右子树”，上一个指针表示“左子树”。如果你被允许这样做，下面是一种非常酷的实现tree sort的方法：
1.创建一个新的指向链表单元格的指针，它将作为树根的指针。 2.对于双向链表的每个元素： 1）从链表中删除该单元格。 2）将该单元格视为BST节点，将节点插入二叉搜索树中。 3.进行BST的中序遍历。每当你访问一个节点时，将其从BST中删除并重新插入到双向链表中。
这个算法在最好情况下以 O(n log n) 的时间复杂度运行，在最坏情况下以 O(n2) 的时间复杂度运行。就内存使用而言，前两步只需要 O(1) 的内存，因为我们正在重复利用旧指针的空间。最后一步也可以使用一些特别聪明的算法在 O(1) 的空间中完成。
你也可以考虑以这种方式实现 堆排序，不过有点棘手。
希望这有所帮助！
- templatetypedef
6
这就是我想表达的，但你说得比我好多了！:O) - Richard Baxter
除非我错了，qsort 在链表是双向链接时运行良好/可以。可能需要指出这一点。 - Thomas Eding
@trinithis- 是的，没错。我的重点大多是指出，在处理数组情况时，快速排序并没有得到由局部性带来的巨大性能提升，使其在所有 O(n log n) 排序中表现最佳。 - templatetypedef
请问您能否解释一下合并步骤的时间复杂度？ - CodeYogi
@CodeYogi 合并两个已排序的链表，就像合并两个已排序的数组一样，可以在O(n)的时间内完成，其中n是列表中元素的总数。您只需要存储尾指针即可。 - templatetypedef
维基百科上的链表归并排序文章现在包括了一种更快的自底向上的链表归并排序，它使用一个小型（25到32个）指向节点的指针（或引用）数组。这比需要重复扫描子列表以便分割它们的自顶向下的归并排序快大约两倍。在这种情况下，所有3个列表都可以合并到数组中（因为这部分是逐个节点完成的），然后将数组合并成单个列表。 - rcgldr
0
如果这三个列表是单独排序的，那么问题就很简单了，但是它们没有排序，因此会稍微麻烦一些。
我会编写一个函数，该函数接受一个已排序的列表和一个未排序的列表作为参数，逐个遍历未排序列表中的每个项目，并按顺序将其添加到排序列表中的正确位置，直到未排序列表中没有项目为止。
然后简单地创建第四个“空”列表，由于它是空的，因此自然是“排序”的，然后使用每个未排序列表依次调用您的方法三次。
将列表转换为数组可能会使事情更有效率，以便能够使用更高级的排序技术，但是必须考虑将其转换为数组的成本，并与原始列表的大小进行平衡。
- Richard Baxter
0
我认为你可以应用快速排序。它与归并排序几乎相同，唯一的区别是你首先分割然后合并，在快速排序中，你首先“合并”，然后再进行分割。如果你看起来有点不同，就是归并排序和快速排序在相反的方向上。
归并排序：
分割 -> 递归 -> 合并
快速排序：
反合并（相对于合并） -> 递归 -> 反分割（相对于分割）
- Luka Rahne
-1
@templatetypedef所描述的归并排序算法不是O(n lg n)。因为链表不是随机访问的，步骤2.1 将列表拆分为大约相等大小的两个列表 实际上意味着一个O(n^2 log n)的整体算法来对列表进行排序。仔细想一想。
这里有一个链接，使用归并排序将链表排序，首先将元素读入数组中 -- http://www.geekviewpoint.com/java/singly_linked_list/sort。
- kasavbere
1
3如我在您回答另一个问题的评论中所提到的，这是不正确的。进行分裂所需的线性工作不会增加渐近运行时间，因为在合并步骤中已经有线性工作在进行。递归关系完全相同。历史上，归并排序是为了在磁带驱动器上使用（在许多方面类似于链表）而发明的，并改进了朴素的O(n^2)排序算法，这就是为什么要使用它的原因。 - templatetypedef
-7
对于链表来说，没有高效的排序算法。 可以先将链表转换为数组，进行排序，再重新链接成链表。
- ddyer
6
4嗯...归并排序运行得很好。唯一的技巧是要找出如何高效地划分列表。例如：http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html。 - dmckee --- ex-moderator kitten
@dmckee - 如果列表已经排序，归并排序才能正常工作——在这种情况下，这三个列表最初是未排序的，所以第一步应该是对链接列表进行排序，然后合并它们——如果内存不是问题，那么创建一个指针数组，对指针进行排序，然后创建一个新的链接列表会更有效率。 - Soren
1Soren：归并排序可用于未排序的列表，然后可以使用合并函数/方法/工具将它们组合。 - dmckee --- ex-moderator kitten
1我在我的Haskell程序中经常使用归并排序。它被称为
Data.List.sort。它的时间复杂度为O(nlogn)，运行效率高。 - Thomas Eding从未排序的列表开始，基于列表的任何排序都是O(n)。 - ddyer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接