java - 队列上的快速排序？

Question

我被要求这样做:

但是所有快速排序的例子都使用数组吗？我在这里看到过其他帖子，说这是可能的，但没有真正解释如何实现？我已经得到了“使用链表”的队列和类的实现。

Answer 1

真正的快速排序需要能够交换元素，这对于队列来说不容易完成，可能需要将队列的一部分移动到临时队列才能“交换”元素。

类似快速排序的算法可用于像队列这样的 FIFO 类型容器。第一个元素可以用作枢轴，然后创建 3 个队列，一个用于元素 < 枢轴，一个用于元素 == 枢轴，一个用于元素 > 枢轴。对于元素!=pivot的两个队列使用递归，然后将这3个队列“串联”形成一个排序队列。其他元素可用于枢轴，但这将涉及循环队列以访问枢轴的目标元素。

评论 - 当仅限于 FIFO 容器时，合并排序更有意义。当仅限于 LIFO(堆栈)类容器时，也可以使用合并排序(至少需要 3 个 LIFO 容器(如果使用基于多相的合并排序，则比较复杂)，4 个 LIFO 容器更直接)。