寻找具有尽可能少的比较操作的排序算法

Question

寻找具有尽可能少的比较操作的排序算法

gyr*_*olf 11 sorting algorithm

我想对人类进行比较的项目进行排序:

图片
工作项目的优先顺序
...

对于这些任务,比较次数是性能的限制因素.

什么是需要比较的最小数量(我假设> ñ为ñ项目)？
哪种算法保证这个最小数量？

Answer 1

Sma*_*acL 5

鸽子洞分类是N阶,如果数据可以被打孔,则可以很好地与人类一起使用.一个很好的例子就是在选举中计票.

Answer 2

Con*_*lls 5

从我曾经做过的关于这个主题的作业中......

比较计数适用于以随机顺序对数据进行操作的各种排序算法

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

Run Code Online (Sandbox Code Playgroud)

这些比较计数适用于对开始“接近排序”的数据进行操作的各种排序算法。除此之外，它还展示了快速排序的病态情况。

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

Run Code Online (Sandbox Code Playgroud)

由此我们可以看出，从比较次数来看，归并排序是最好的。

我不记得对快速排序算法的修改是什么，但我相信一旦单个块减小到一定大小，它就会使用插入排序。通常这样做是为了优化快速排序。

您可能还想查找 Tadao Takaoka 的“最小归并排序”，这是归并排序的更有效版本。

Answer 3

Ian*_*Ian 5

要回答这个问题,我们需要做出很多假设.

让我们假设我们正在通过可爱来分类图片.目标是在最短的时间内从人类获得最大可用信息.这种交互将主导所有其他计算,因此它是唯一重要的计算.

正如其他人提到的,人类可以很好地处理在一次互动中订购几件物品.假设我们每轮可以获得相对顺序的八个项目.

每轮将七条边引入有向图中,其中节点是图片.如果节点A可从节点B到达,则节点A比节点B更可靠.记住该图.

现在,让我告诉你一个海军和空军解决问题的方法.他们都希望快速获得一群人的身高.海军告诉人们排队,然后如果你比你面前的人短,切换位置,重复直到完成.在最坏的情况下,它是N*N的比较.

空军告诉人们站在正方形的格子里.他们在sqrt(N)人身上一对一地进行洗牌,这意味着最坏的情况是sqrt(N)*sqrt(N)== N比较.然而,人们只是沿着一个维度排序.因此,人们面朝左,然后再做同样的洗牌.现在我们进行了2*N比较,但这种情况仍然不完善,但对政府工作来说已经足够了.有一个短角,对面有一个高角,有一个清晰的对角线高度梯度.

如果你不关心完美,你可以看到空军方法如何在更短的时间内获得结果.您还可以看到如何有效地获得完美.你已经知道,最短和最长的男人都在两个角落里.第二短的可能在最短的后面或旁边,第三短的可能在他后面或旁边.一般来说,某人的身高等级也是他从短角落到曼哈顿的最大距离.

回顾图形类比,呈现每轮的八个节点是具有当前最常见的最长入站路径长度的八个节点.最长入站路径的长度也表示节点的最小可能排序等级.

您将按照此计划使用大量CPU,但您将尽可能充分利用您的人力资源.

回想起来，可爱循环绝对是可能的。 (2认同)

Answer 4

Jon*_*eet 1

我认为您不可能得到比有关排序的维基百科页面更好的答案。

概括：

对于任意比较（不能使用基数排序之类的东西），您可以实现的最好结果是 O(n log n)
各种算法可以实现这一点 - 请参阅“算法比较”部分。
常用的快速排序在典型情况下是O(n log n)，但在最坏情况下是O(n^2)；通常有很多方法可以避免这种情况，但如果您真的担心比较的成本，我会选择 MergeSort 或 HeapSort 之类的方法。它部分取决于您现有的数据结构。

如果人类进行比较，他们是否也在进行排序？您是否需要使用固定的数据结构，或者您可以使用平衡二叉树插入排序有效地创建副本吗？存储要求是什么？

因此，我的第一点的“任意比较”部分。 (3认同)

归档时间：	16 年，7 月前
查看次数：	2775 次
最近记录：	12 年，10 月前