二元选择评级的排序算法

Question

想象一下，我有一个书籍清单，我想按照自己的喜好程度进行排序。与其对每本书进行评分，我选择从列表中随机选择两本书中最好的一本，并重复此过程，直到完成所需的比较（不对所有组合进行评分）。

如何根据这种二元选择对我的书籍清单进行排序？这个问题有官方名称吗？

- Amber Bock

---

当你说“随机选择”时，是指你对所选书籍没有选择权吗？还是可以任意选择想要的书籍？ - templatetypedef

我的意思是我无法选择哪些书被选中。它们是从列表中随机选择的。 - Amber Bock

Answer 1

正如Jonas Elfström所指出的，Fisher-Yates是洗牌集合的规范方式，这可能是一个好主意，因为它将允许您获取每个项的数据。不过我认为您可能需要多次通过。本质上，当对项目集进行排序时，正在构建一个有向图，其中节点是项目，边表示关系“大于或等于”。当可以算法地定义此关系时，那么单次通过就足够了，并且您将得到一个良好的排序集。

问题在于，人们很容易相信，看两本书并让人决定而没有明确定义的算法，人们会得到这样一种情况：A > B，B > C和C > A。这显然不会产生一个良好的排序集。更糟糕的是，在两个不同的日子里，人们可能会对同样的两本书给出两个不同的答案。

我能想到的最好方法是维护一个n x n矩阵，其中n是要排序的项目数。 i，j条目是选择项目i作为比项目j更好的次数。这里，i索引行，j索引列。

从这里开始，PageRank(不幸的是被专利保护)是理想的。不够优雅，但可能足够好的是，根据a_ij和a_ji之间的差异之和对书籍进行排序。例如，对三本书进行排序。

   A B C
   _ _ _
 A|0 3 2
 B|2 0 3
 C|1 2 0

这意味着A被评为比B更好3次，比C更好2次。将行求和得到

 A: (AB - BA) + (AC - CA) = (3 - 2) + (2 - 1) = 2
 B: (BA - AB) + (BC - CB) = (2 - 3) + (3 - 2) = 0
 C: (CA - AC) + (CB - BC) = (1 - 2) + (2 - 3) = -2

所以它们将按照 A > B > C 的顺序排序。

---

如果您不使用页面排名，则可以消除矩阵并通过为每本书关联初始化为0的整数来获得相同的结果。当选择A而非B时，增加与A相关联的整数，并减少与B相关联的整数。 ^{1 抱歉发牢骚，但我不知道如何申请基本上是数学结果的专利。}

- aaronasterling

Answer 2

抱歉搬起老问题，但我认为这对你很有用。

当我处理同样的任务时，我选择了在线插入排序。这是小集合的完美选择。例如，对于10本书，您只需要进行14次比较（平均情况下）。在最佳情况下，您只需要进行9次比较（如果您的集合已经排序）。

如果您选择快速排序，则应进行20次比较（平均情况下），但它总是比脏排序更好（通过将每本书与收藏中的所有书进行比较）。

无论如何，您都应该进行在线排名（基于先前比较结果的下一对选择）。

请注意，所有这些解决方案都对传递关系做出了一个假设（如果书1比书2好，书2比书3好，那么书1比书3好）。如果它对您不起作用-您无法对它们进行排名。

您可以在维基百科上找到两种算法的完美描述：
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Quick_sort

- Gleb M Borisov

Answer 3

你可以对这些书进行费舍尔-耶茨洗牌算法，然后再两两取出。仅比较两个实例要么是勉强称之为排序，要么可以说是核心部分。

- Jonas Elfström

---

谢谢！那应该可以，但我会等一段时间再选择答案，看看其他人可能会想到什么。 - Amber Bock