sorting - 排序中的最少比较次数

Question

我有 32 只不同重量的兔子，我想按重量对它们进行分类。我可以使用每次重 2 只兔子的重量，并告诉我哪只兔子更轻。我需要对所有兔子进行排序的最少比较次数是多少，使用哪种算法？

例如，如果我使用快速排序，我需要进行 32*32（最坏情况下为 n^2）比较，这可能不是这个问题比较最少的算法。

Answer 1

我可能不记得快速排序是如何工作的，但这是我要做的：

取成对的值，并按顺序（1-2、3-4 等）对它们进行排序。这将创建 16 个“短排序队列”。现在比较相邻队列的顶部元素；然后是“顶部的一个”和剩余的顶部；继续按照你的方式工作。这最多需要 3 次比较。对其他对重复; 到目前为止的总数 = 8 + 4*3 = 20

同样的道理，我们现在有 4 组 4 只分类的兔子，我们最多将它们分类为 7 步，每组分为两组，每组 8 只，另外 14 只；然后是 2 组 8 组，我们按 15 排序。总数：8+12+14+15 = 49。

仅显示四个（原理相同）：

假设我们有兔子 ABCD，按重量降序排列（我们不知道……我们希望它们按升序排列）。算法：

比较 A 和 B - 现在是 BA

比较 C 和 D - 现在是 DC

比较 BD - D 最轻，排在最前面

比较 BC - C 更轻，下一个

现在放 B（已经知道它比 A 轻）最后放 A

如您所见，总共进行了4次比较...