在队列上使用排序算法？

Question

我使用基于单链表的队列抽象数据类型。我想以三种方式对Queue保留的数据进行排序：首先用合并排序，第二用快速排序，第三用堆排序。那么有没有人可以提供帮助？

Answer 1

通常，队列按插入顺序排序 - 项目按其插入队列的顺序排序。看起来你想打破队列的基本质量。

我只打算用这个答案来覆盖合并排序。希望其他人会覆盖其他算法，或者你可以自己派生它们。

只需知道一个列表何时结束，另一个列表何时开始，单个链接列表就可以视为列表列表。对于合并排序，您需要从排序列表开始 - 如果每个列表的长度都为1，则排序只是因为没有其他顺序是可能的。将两个链表合并成一个很容易 - 从两个列表中选取最小的项目并将其链接到一个新列表，直到两个列表都用尽。因此，对于第一遍，您将列表分为长度为1的子列表，并将它们组合为长度为2的子列表。第二遍将长度为2的子列表合并为长度为4的子列表。每次传递将有序子列表的大小加倍。当排序的子列表的大小大于或等于整个列表的大小时，您就完成了。