当需要用户输入进行比较时，最好的排序算法是什么？

Question

当实际比较计数不是问题但计算机不知道如何比较，因此需要用户输入时，我试图提出最佳排序算法。

例如，假设有一系列食物，

[apple, banana, orange, pear]

，我们想将其从最好到最差进行排序。要知道 apple 或 banana 哪个更好，用户需要回答。但是，如果我们知道 apple 优于 banana 且 banana 优于 orange（=用户已为这些比较提供输入），则无需输入即可比较 apple 和 orange。

可以使用什么样的排序算法来最大限度地减少我们要求用户输入的次数？

Answer 1

忘记排序算法，您真正想要的是首先在所有元素之间建立关系，然后您将能够应用任何排序算法

这种关系的最简单形式是方阵，其中所有单元格都有值，因此您的目标是用最少数量的问题填充矩阵（请注意，您实际上只需要该矩阵的上三角形或下三角形，因为

if a>b then b<a

）

例如让我们从“苹果香蕉”开始：

你有空单元格，所以你问下一个问题“香蕉橙”，这样你就可以在表格中添加这些信息

在此步骤中，您可以使用规则

if a<b and b<c then a<c

（或逆

a>b and b>c then a>c

）

自动填充更多单元格，而无需提出问题

然后您可以继续询问有关任何空单元格的问题，并在所有内容都填满时停止，然后您可以运行快速排序或任何其他

问题的顺序应该沿着主对角线，所以：