algorithm - 以尽可能少的比较对元素进行排序

Question

我有一个装满图像的文件夹。太多了，无法仅“排名”。我制作了一个程序，一次显示两个，让用户选择两个中哪个更好。最后，我希望所有照片都按从好到坏的顺序排列。

我纯粹是在尝试优化尽可能少的比较。我不在乎程序是否在 n 立方时间内运行。我在这里阅读了其他有类似问题的问题，但我正在寻找更高级的东西。

我在想也许是某种基于您已经进行的比较的算法，该程序选择两个图像进行比较，这些图像将提供最多的信息。甚至可能是建立复杂连接以帮助确定订单和潜在订单的算法。

就像我说的那样，我不在乎它是否慢只是纯粹试图尽量减少比较

Answer 1

如果存在全序，则至少需要 nlog2(n) 次比较。从数学上很容易证明。没办法。因此，nlog(n) 中的常规排序算法将完成这项工作。

您正在尝试做的事情称为“拓扑排序”。谷歌它并在wikipedia中阅读它.您可以通过较少的比较实现部分排序。它有点像研究生。您获得的比较越多，结果就越好。

但是，如果不存在全序怎么办？人类无法为主观任务生成总顺序。 例如图片 1 比 2 好，2 比 3 好，但 3 比 1 好。 在这种情况下，没有任何排序算法可以产生匹配所有决策的排列。在拓扑排序过程中，您可以检测到那些不一致的决策并消除它们。