想象一下,我有一个书籍清单,我想按照自己的喜好程度进行排序。与其对每本书进行评分,我选择从列表中随机选择两本书中最好的一本,并重复此过程,直到完成所需的比较(不对所有组合进行评分)。
如何根据这种二元选择对我的书籍清单进行排序?这个问题有官方名称吗?
想象一下,我有一个书籍清单,我想按照自己的喜好程度进行排序。与其对每本书进行评分,我选择从列表中随机选择两本书中最好的一本,并重复此过程,直到完成所需的比较(不对所有组合进行评分)。
如何根据这种二元选择对我的书籍清单进行排序?这个问题有官方名称吗?
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
的顺序排序。
A
而非B
时,增加与A
相关联的整数,并减少与B
相关联的整数。
1 抱歉发牢骚,但我不知道如何申请基本上是数学结果的专利。
抱歉搬起老问题,但我认为这对你很有用。
当我处理同样的任务时,我选择了在线插入排序。这是小集合的完美选择。例如,对于10本书,您只需要进行14次比较(平均情况下)。在最佳情况下,您只需要进行9次比较(如果您的集合已经排序)。
如果您选择快速排序,则应进行20次比较(平均情况下),但它总是比脏排序更好(通过将每本书与收藏中的所有书进行比较)。
无论如何,您都应该进行在线排名(基于先前比较结果的下一对选择)。
请注意,所有这些解决方案都对传递关系做出了一个假设(如果书1比书2好,书2比书3好,那么书1比书3好)。如果它对您不起作用-您无法对它们进行排名。
您可以在维基百科上找到两种算法的完美描述:
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Quick_sort