假设我拥有100个视频游戏,并且希望将其从最喜欢的到最不喜欢的订购。很难为每个视频游戏提供一个代表我喜欢它的数值,因此我想将它们相互比较。

我想出的一种解决方案是挑选2个随机视频游戏,然后选择我更喜欢的一个,然后丢弃另一个。不幸的是,此解决方案仅使我知道第一名的视频游戏,因为那将是最后一个,并且几乎没有提供有关其他游戏的信息。然后,我可以对其他99个视频游戏重复该过程,以此类推,但这是非常不切实际的:O(n ^ 2)。

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

最佳答案

您可以使用quicksort又称为数据透视排序。选择一个游戏,然后将其他所有游戏与之进行比较,这样您就可以得到一组较差的游戏和较出色的游戏。递归地重复每一半。平均案例性能为n log n。

http://en.wikipedia.org/wiki/Quicksort

关于algorithm - 快速相对排名算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/17686253/

10-11 23:00
查看更多