我希望对人为进行比较的项目进行排序:
- 图片
- 工作项目的优先级
- ...
对于这些任务,比较次数是性能的限制因素。
- 需要的最小比较次数是多少(我假设对于N个项目,会有 > N次比较)?
- 哪种算法保证了这个最小数量的比较次数?
我希望对人为进行比较的项目进行排序:
对于这些任务,比较次数是性能的限制因素。
Size QkSort HpSort MrgSort ModQk InsrtSort
2500 31388 48792 25105 27646 1554230
5000 67818 107632 55216 65706 6082243
10000 153838 235641 120394 141623 25430257
20000 320535 510824 260995 300319 100361684
40000 759202 1101835 561676 685937
80000 1561245 2363171 1203335 1438017
160000 3295500 5045861 2567554 3047186
Size QkSort HpSort MrgSort ModQk InsrtSort
2500 72029 46428 16001 70618 76050
5000 181370 102934 34503 190391 3016042
10000 383228 226223 74006 303128 12793735
20000 940771 491648 158015 744557 50456526
40000 2208720 1065689 336031 1634659
80000 4669465 2289350 712062 3820384
160000 11748287 4878598 1504127 10173850
从这里我们可以看出,归并排序在比较次数方面是最好的。
我记不得快速排序算法的修改了,但我相信它是使用插入排序一旦单个块缩小到一定大小时。这种优化快速排序的方法很常见。
您还可以查找Tadao Takaoka的'Minimal Merge Sort',这是归并排序的更高效版本。
您需要考虑人类可能进行非传递性比较,例如他们喜欢A胜过B,B胜过C,但也喜欢C胜过A。因此,在选择排序算法时,请确保它不会在发生这种情况时完全崩溃。
人们很擅长将5-10个物品从好到坏进行排序,并且在这样做时得出的结果更加一致。我认为尝试应用经典的排序算法可能不起作用,因为通常采用基于人类多重比较的方法。
我认为应该采用轮流比较的方法,每次将物品分成最一致的组。每次迭代只会使结果更加确定。
这也很有趣 :)
我认为你不太可能得到比排序维基百科页面更好的答案。
摘要:
如果人类进行比较,他们也会进行排序吗?你是否有一个需要使用的固定数据结构,还是可以使用平衡二叉树插入排序有效地创建副本?存储要求是什么?
这里有一个算法比较。两个更好的候选者是快速排序和归并排序。快速排序通常更好,但最坏情况下性能较差。
归并排序绝对是这里的最佳选择,因为您可以使用Map/Reduce类型的算法让多个人并行进行比较。
快速排序本质上是单线程排序算法。
您还可以调整归并排序算法,使其不再比较两个对象,而是向人类展示一组包含五个项目的列表,并要求他或她对它们进行排名。
另一个可能性是使用著名的“Hot or Not”网站所使用的排名系统。这需要更多的比较,但是比较可以以任何顺序并行进行,只要您有足够的人类资源,这将比经典排序更快。
这个问题实际上引发了更多的问题。
我们是在谈论一个人进行比较吗?如果你在谈论一群人试图按顺序排列物体,那么这将是一个非常不同的挑战。
那么信任和错误的问题呢?并不是每个人都可以被信任或者做到完全正确 - 如果在任何给定的时刻提供了错误的答案,某些类型的问题会出现灾难性的错误。
主观性呢?“按可爱程度对这些图片进行排序”。一旦你到达这个点,它就可能变得非常复杂。正如其他人所提到的,像“热门或不热门”这样的东西在概念上最简单,但效率并不高。在最复杂的情况下,我认为谷歌是一种将对象排序的方式,其中搜索引擎推断出人类所做的比较。