在 C 中对链表进行排序 [英] Sorting linked lists in C

问题描述

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

I was asked to write a function that takes 3 unsorted linked lists and returns one single sorted linked list that combines all three lists. What is the best way you can think of?

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

I don't really have restrictions of memory, but what would you do with/without memory restrictions?

推荐答案

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

One option would be to use merge sort on all three of the linked lists, then use one final merge step to merge them together into an overall sorted list.

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

Unlike most O(n log n) sorting algorithms, merge sort can run efficiently on linked lists. At a high-level, the intuition behind merge sort on a linked list is as follows:

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

1. 将列表分成大小大致相等的两个列表，可能是将奇数元素移动到一个列表中，将偶数元素移动到另一个列表中.
2. 递归地使用归并排序对这些列表进行排序.
3. 应用合并步骤将这些列表合并为一个排序列表.

1. Split the list into two lists of roughly equal size, perhaps by moving odd elements into one list and even elements into the other.
2. Recursively use merge sort to sort those lists.
3. Apply a merge step to combine those lists into one sorted list.

链表上的合并算法真的很漂亮.伪代码大致如下:

The merge algorithm on linked lists is really beautiful. The pseudocode works roughly like this:

1. 初始化一个包含结果的空链表.
2. 只要两个列表都不为空:

1. Initialize an empty linked list holding the result.
2. As long as both lists aren't empty:

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

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

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

This can be made to run in O(n) time, so the overall complexity of the merge sort is O(n log n).

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

Once you've sorted all three lists independently, you can apply the merge algorithm to combine the three lists into one final sorted list. Alternatively, you could consider concatenating together all three linked lists, then using a giant merge sort pass to sort all of the lists at the same time. There's no clear "right way" to do this; it's really up to you.

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

The above algorithm runs in Θ(n log n) time. It also uses only Θ(log n) memory, since it allocates no new linked list cells and just needs space in each stack frame to store pointers to the various lists. Since the recursion depth is Θ(log n), the memory usage is Θ(log n) as well.

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

Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. Although the linked list version of quicksort is fast (still O(n log n) expected), it isn't nearly as fast as the in-place version that works on arrays due to the lack of locality effects from array elements being stored contiguously. However, it's a very beautiful algorithm as applied to lists.

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

The intuition behind quicksort is as follows:

1. 如果您有一个零元素或一个元素的列表，则该列表已排序.
2. 否则:

1. 选择列表中的某个元素作为枢轴.
2. 将列表分成三组 - 小于枢轴的元素、等于枢轴的元素和大于枢轴的元素.
3. 递归排序较小和较大的元素.
4. 将三个列表依次连接成更小、相等、然后更大的列表，以返回整个排序列表.

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

One of the nice aspects of the linked-list version of quicksort is that the partitioning step is substantially easier than in the array case. After you've chosen a pivot (details a bit later), you can do the partitioning step by creating three empty lists for the less-than, equal-to, and greater-than lists, then doing a linear scan over the original linked list. You can then append/prepend each linked list node to the linked list corresponding to the original bucket.

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

The one challenge in getting this working is picking a good pivot element. It's well known that quicksort can degenerate to O(n²) time if the choice of pivot is bad, but it is also known that if you pick a pivot element at random the runtime is O(n log n) with high probability. In an array this is easy (just pick a random array index), but in the linked list case is trickier. The easiest way to do this is to pick a random number between 0 and the length of the list, then choose that element of the list in O(n) time. Alternatively, there are some pretty cool methods for picking an element at random out of a linked list; one such algorithm is described here.

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

If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n²) time in the worst case (though it also has O(n) best-case behavior), so it's probably not a good choice unless you specifically want to avoid merge sort.

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

The idea behind the insertion sort algorithm is as follows:

1. 初始化一个包含结果的空链表.
2. 对于三个链表中的每一个:

1. Initialize an empty linked list holding the result.
2. For each of the three linked lists:

1. 虽然链表不为空:

1. While that linked list isn't empty:

1. 扫描结果列表以找到此链表的第一个元素所属的位置.
2. 在该位置插入元素.

<小时>

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

---

Another O(n²) sorting algorithm that can be adapted for linked lists is selection sort. This can be implemented very easily (assuming you have a doubly-linked list) by using this algorithm:

1. 初始化一个包含结果的空列表.
2. 虽然输入列表不为空:

1. Initialize an empty list holding the result.
2. While the input list is not empty:

1. 扫描链表，寻找最小的剩余元素.
2. 从链表中删除该元素.
3. 将该元素附加到结果列表中.

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

This also runs in O(n²) time and uses only O(1) space, but in practice it's slower than insertion sort; in particular, it always runs in Θ(n²) time.

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

Depending on how the linked lists are structured, you might be able to get away with some extremely awesome hacks. In particular, if you are given doubly-linked lists, then you have space for two pointers in each of your linked list cells. Given that, you can reinterpret the meaning of those pointers to do some pretty ridiculous sorting tricks.

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

As a simple example, let's see how we could implement tree sort using the linked list cells. The idea is as follows. When the linked list cells are stored in a linked list, the next and previous pointers have their original meaning. However, our goal will be to iteratively pull the linked list cells out of the linked list, then reinterpret them as nodes a in binary search tree, where the next pointer means "right subtree" and the previous pointer means "left subtree." If you're allowed to do this, here's a really cool way to implement tree sort:

1. 创建一个指向链表单元格的新指针，该单元格将用作指向树根的指针.
2. 对于双向链表的每个元素:

1. Create a new pointer to a linked list cell that will serve as the pointer to the root of the tree.
2. For each element of the doubly-linked list:

1. 从链接列表中删除该单元格.
2. 将该单元格视为 BST 节点，将该节点插入到二叉搜索树中.

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

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

This runs in best-case O(n log n) time and worst-case O(n²). In terms of memory usage, the first two steps require only O(1) memory, since we're recycling space from the older pointers. The last step can be done in O(1) space as well using some particularly clever algorithms.

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

You could also consider implementing heap sort this way as well, though it's a bit tricky.

希望这有帮助！

这篇关于在 C 中对链表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！