快速相对排名算法

Question

假设我拥有100个视频游戏,我想从最喜欢到最不喜欢的顺序订购它们.很难给每个视频游戏一个表示我喜欢它的数值,所以我想把它们相互比较.

我想出的一个解决方案是挑选2个随机视频游戏,然后选择我喜欢哪一个,并丢弃另一个.不幸的是,这个解决方案只让我知道#1视频游戏,因为那将是剩下的最后一个,并提供关于其他的很少的信息.然后我可以为其他99个视频游戏重复这个过程,依此类推,但这是非常不切实际的:O(n ^ 2).

是否有任何O(n)(或只是合理的)算法可用于根据相对标准对数据进行排序？

Answer 1

您可以使用快速排序（也称为枢轴排序）。选择一款游戏，然后将所有其他游戏与它进行比较，这样你就有了一组更差的游戏和更好的游戏。递归地重复每一半。平均情况性能为 n log n。