algorithm - 什么是双重排序

Question

有人可以准确解释什么是双重排序算法以及它是如何工作的吗？我在网上搜索过，但找不到任何关于它的信息。我有一个家庭作业，我想解释它是什么并编写一个使用双重排序对列表进行排序的程序。

谢谢你的帮助！

Answer 1

双轴快速排序具有 2 个轴的概念，与常规快速排序非常相似。有一些选择枢轴的变体让我们假设一个随机选择，而不是算法将类似于以下（我不会给出明确的代码，因为它毕竟仍然是家庭作业）。基本思想是选择随机枢轴 p1 和 p2。假设 p1 <= p2 否则交换它们的值。现在将数组排序为三个部分。第一个将小于 p1，第二个是介于或等于 p1 和 p2 之间的元素，第三个是大于 p2 的元素。比在每个部分上递归。

渐近地，正如您可能猜到的那样，知道一种 O(n lg n) 是最优的，该算法与快速排序同时运行。