list - 通过一次显示两个项目，根据用户的偏好对列表项目进行排名的最有效方法是什么？

Question

对于某些情况，我建议观看 Tom Scott 的这段视频，他在其中确定什么是最好的“东西”:https://youtu.be/ALy6e7GbDRQ .我认为这将有助于解释我的问题。

---

基本上，我正在尝试制作一个算法/程序，让一个用户通过一次在两个项目中选择他最喜欢的一个来对列表中的所有项目进行排名。

例如，最基本的列表包含 3 个项目:A、B 和 C。 操作顺序如下所示:

1. 用户可以选择:A 或 C。
2. 他更喜欢 C。
3. 用户可以选择:B 或 C。
4. 他更喜欢 C。
5. 用户可以选择:A 或 B。
6. 他更喜欢 A。

所以我们知道3次比较的排序顺序是[C > A > B]。

但是，如果在第 4 步，用户会选择 B 怎么办？我们可以通过逻辑假设他在第 5 步之前更喜欢 B 而不是 A。因此我们知道排名列表将是 [B > C > A] 仅在 2 比较中并且它与第一种情况一样准确。因此，我们可以看到步骤数取决于用户的选择。

---

那么在最少数量的比较中对所有项目进行排名的正确或最有效的方法是什么？我考虑过从字面上比较每一种可能的组合，并为每次选择一个项目而不是另一个项目时上升的每个项目设置一个计数器。但是通过这种方式，要进行的比较的数量只会根据列表的大小呈指数增长，并且它不会像上面的示例那样是最有效的方式。我还考虑过使用一种简单的排序算法，用户可以在其中“手动”进行比较，但我对一般的排序算法不是很熟悉。

在 Tom Scott 的视频中，该网站随机挑选了两个项目，他使用了如此庞大的用户群，以至于问题只是通过概率和统计自行纠正，他不需要担心每个项目都被平等地挑选出来准确的。由于我只希望一个用户对项目进行排名，因此我需要找到一种方法来选择正确的项目进行比较，以尽可能提高效率(我认为)。另一个区别是我不会像 Tom 的版本那样拥有超过 7000 个项目。我想用它来排名，例如“所有迪士尼电影”、“某些音乐类型”或“所有塞尔达电子游戏”，所以我我很确定我将拥有 ma​​x 大约 100 件元素。

我的问题是:我走在正确的轨道上吗？我应该使用简单的排序算法(如果是，我应该使用哪一个？)或者唯一有效地做到这一点的数学方法是比较每个组合？还是我错过了一些可以帮助我的东西？如果我对每个组合进行暴力破解，这显然是对项目进行排名的最简单和准确的方法，但肯定不是最有效的。我想比较的顺序和我们比较的项目对于最有效来说真的很重要，这就是我迷路的地方。

我知道在这里问这不是一个真正的传统问题，但感谢您帮助我或引导我走上正确的道路。

Answer 1

假设用户将创建项目的总排序，算法应该维护一个完全排序的列表，其中包含越来越多的项目。获取下一个无序项并使用二进制搜索所需的比较将其插入有序列表。

获取下一个未排序的项目并使用两个项目的二进制搜索比较来插入它。

重复直到所有项目都被订购。

二分搜索应该尽量减少每个阶段的比较，并随着时间的推移向用户呈现每个新项目的更有意义的比较。