寻找一种尽可能少比较操作的排序算法。

Question

寻找一种尽可能少比较操作的排序算法。

algorithmsorting

12

我希望对人为进行比较的项目进行排序：

图片
工作项目的优先级
...

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

需要的最小比较次数是多少（我假设对于N个项目，会有 > N次比较）？
哪种算法保证了这个最小数量的比较次数？

- gyrolf

1

这个人是同时在进行排序和比较，还是只是在进行比较？在这方面，有些排序方式比其他的“更容易”，这会影响我的选择。 - SmacL

如果你谈论的是那些人们在分类时还必须移动的实体物品，不要低估洗牌物品所需的成本。 - David Z

我假设排序是由一台计算机使用众所周知的排序算法完成的。没有移动任何物理对象。 - gyrolf

@David，说得好。获取和存储的人类等价物可能比比较的等价物更昂贵。比较的成本还取决于所考虑对象的类型和可能变化的数量。按价值排序硬币只比按重量排序沙子稍微容易一点 ;) - SmacL

重复的使用最少比较排序数组 - Janus Troelsen

11个回答

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

这些比较计数是针对在数据“几乎排序”时运行的各种排序算法的。其中，它展示了快速排序的病态情况等内容。

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'，这是归并排序的更高效版本。

- ConcernedOfTunbridgeWells

4

鸽巢排序是一种O(N)的排序方法，如果数据可以被归类整理，那么对于人类来说这种方法非常实用。例如，在选举中计票就是一个很好的应用场景。

- SmacL

3

您需要考虑人类可能进行非传递性比较，例如他们喜欢A胜过B，B胜过C，但也喜欢C胜过A。因此，在选择排序算法时，请确保它不会在发生这种情况时完全崩溃。

- Erich Kitzmueller

这可能更适合作为注释而不是答案，但它仍然是一个重要的观点。 - R.. GitHub STOP HELPING ICE

1

绝对正确，但看看日期……那时候规则没有那么严格。 - Erich Kitzmueller

3

人们很擅长将5-10个物品从好到坏进行排序，并且在这样做时得出的结果更加一致。我认为尝试应用经典的排序算法可能不起作用，因为通常采用基于人类多重比较的方法。

我认为应该采用轮流比较的方法，每次将物品分成最一致的组。每次迭代只会使结果更加确定。

这也很有趣 :)

- Alex Gartrell

1

这是一个有趣的观点。大多数排序算法一次只比较两个元素，而人们似乎能够相对快速地排列少量的项目。也许我们有点类似；）顺便说一句，桶排序和鸽巢排序基本上是一样的东西。 - SmacL

2

如果比较操作相对于记账成本来说很昂贵，您可以尝试以下算法，我称之为“锦标赛排序”。首先，一些定义：

1.每个节点都有一个数字“得分”属性（必须能够容纳从1到节点数的值），以及“上次击败”和“同行失败者”属性，它们必须能够容纳节点引用。

2.如果一个节点应该在另一个节点之前输出，则该节点比另一个节点“更好”。

3.如果没有已知比它更好且已输出的元素，则认为元素是“合格的”，如果已知任何未输出的元素比它更好，则认为元素是“不合格的”。

4.节点的“得分”是它已知比它更好的节点数加1。

要运行该算法，请最初为每个节点分配1分。重复比较两个得分最低的合格节点；在每次比较后，将输家标记为“不合格”，并将输家的得分加到获胜者的得分中（输家的得分不变）。将失败者的“同行失败者”属性设置为获胜者的“上次击败者”，将获胜者的“上次击败者”属性设置为输家。迭代此过程，直到只剩下一个合格节点。输出该节点，并使获胜者击败的所有节点都是合格的（使用获胜者的“上次击败者”和“同行失败者”属性链）。然后继续对剩余节点运行该算法。

在有100万个项的情况下，比较次数略低于Quicksort库实现的比较次数；我不确定该算法与更现代化版本的QuickSort相比如何。记账成本很高，但如果比较操作足够昂贵，则可能会节省成本。该算法的一个有趣特点是它只执行与确定下一个要输出的节点相关的比较；我不知道还有哪种算法具有这个特性。

- supercat

有趣的想法。你是在哪里读到它的，还是自己想出来的？如果是自己想出来的，你会正式发布吗？复杂度分析如何？你有没有考虑过这个想法在现实场景中的应用？这个想法是否可以自然地扩展到多路比较原语？等等。 - Ian

@Ian：我是在观看奥运会后得到这个想法的，当时是在1990年代，在我的办公桌上有一台16MB的电脑。我不认为这是一种实用的排序方法，也不认为它能提供任何特别有用的见解以开发更好的方法，所以我从未觉得值得进行任何特定类型的正式写作。我认为有意义的大型未开发概念可能是有关分区信息的有状态比较器。如果按字母顺序排序，并且知道[simplistic example]所有项目... - supercat

如果一个分区中的项目在HUMBLE和HUMPH之间，那么在比较分区内的项目时就没有必要比较前三个字母。对于短键而言，这不是一个有用的性能增强，但在许多具有长键的实际情况下，数千或数百万个项目的前90％将具有相同的值，并且忽略该部分进行比较可能会提供有用的性能提升。 - supercat

@Ian：顺便说一下，如果你还没有看到的话，这里有一个有趣的小挑战：对于五个项目，需要多少比较才能排序？ - supercat

1

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

摘要：

对于任意比较（无法使用类似于基数排序的东西），最好的成果是O(n log n)。
各种算法都可以实现这一点 - 参见“算法比较”部分。
通常使用的快速排序在典型情况下为O(n log n)，但在最坏情况下为O(n^2）;通常有避免这种情况的方法，但如果你真的担心比较的成本，我会选择像归并排序或堆排序之类的算法。这在一定程度上取决于您现有的数据结构。

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

- Jon Skeet

1

O(n log n) 是最好的通用排序算法。虽然有一些排序算法，如鸽巢排序，时间复杂度为 O(n)，但仅适用于特定类型的数据。 - SmacL

3

因此，“对于任意比较”的部分是我第一点的要点。 - Jon Skeet

很好，但是如果每次比较都需要人类交互来识别图像，我会怀疑许多任意方法的适用性。许多手动排序，例如归档，即使它们未能实现o(n)，也会以此为目标。正如您所问，我们需要了解更多关于问题的具体信息才能给出一个好的答案。 - SmacL

是的 - 这绝对是一个细节能够产生巨大影响的情况。 - Jon Skeet

1

这里有一个算法比较。两个更好的候选者是快速排序和归并排序。快速排序通常更好，但最坏情况下性能较差。

- kgiannakakis

+1 同意... 我通常自己使用快速排序（用于大数据集）和归并排序（用于小数据集）的组合，尽管我从未尝试过弄清楚它是否是最优选择。 - David Z

1

归并排序绝对是这里的最佳选择，因为您可以使用Map/Reduce类型的算法让多个人并行进行比较。

快速排序本质上是单线程排序算法。

您还可以调整归并排序算法，使其不再比较两个对象，而是向人类展示一组包含五个项目的列表，并要求他或她对它们进行排名。

另一个可能性是使用著名的“Hot or Not”网站所使用的排名系统。这需要更多的比较，但是比较可以以任何顺序并行进行，只要您有足够的人类资源，这将比经典排序更快。

- James Anderson

当然，对于归并排序，人类可以立即开始将n/m个项目进行归并排序，而对于快速排序，则需要在开始时有一个“加速”期 - 您需要进行log(m)次分区步骤，才能为m个人提供足够的任务。但是，在算法的末尾，归并排序是否也存在同样的问题？最后一步合并必须由单个人执行，对吗？另一方面，快速排序则一直让每个人忙碌到结束。 - j_random_hacker

1

这个问题实际上引发了更多的问题。

我们是在谈论一个人进行比较吗？如果你在谈论一群人试图按顺序排列物体，那么这将是一个非常不同的挑战。

那么信任和错误的问题呢？并不是每个人都可以被信任或者做到完全正确 - 如果在任何给定的时刻提供了错误的答案，某些类型的问题会出现灾难性的错误。

主观性呢？“按可爱程度对这些图片进行排序”。一旦你到达这个点，它就可能变得非常复杂。正如其他人所提到的，像“热门或不热门”这样的东西在概念上最简单，但效率并不高。在最复杂的情况下，我认为谷歌是一种将对象排序的方式，其中搜索引擎推断出人类所做的比较。

- Cybergibbons

我假设一个人进行比较。因此，我希望他们在一定程度上保持一致（尽管对于人来说可能有限...）。当然，这些比较是主观的，有时可能是错误的。如果有多个人进行（主观）比较，我会使用类似国际象棋ELO评分的方法，正如https://dev59.com/ZHVC5IYBdhLWcg3w2lCI中提到的那样。 - gyrolf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ian · Accepted Answer

为了回答这个问题，我们需要做很多假设。假设我们正在按可爱程度排序图片。目标是在最短时间内从人类那里获取最大可用信息。这个交互将支配所有其他计算，所以它是唯一重要的。

正如其他人提到的，人类可以很好地处理一个交互中的几个项目的排序。假设我们每轮可以获得八个相对顺序的项。

每一轮向有向图引入七条边，其中节点是图片。如果节点A可以从节点B到达，则节点A比节点B更可爱。记住这张图。

现在，让我告诉你海军和空军不同解决问题的例子。他们都希望快速地按身高顺序排列一组人。海军告诉人们排队，然后如果你比前面的人矮，就交换位置，并重复此过程直到完成。最坏情况下，它是N*N次比较。

空军告诉人们站成一个正方形网格。他们在sqrt(N)个人上进行前后洗牌，这意味着最坏情况下sqrt(N)*sqrt(N)== N次比较。然而，这些人只沿一个维度排序。因此，人们面向左边，然后再次执行相同的洗牌。现在我们已经进行了2*N次比较，排序仍然不完美，但对于政府工作来说已经足够好了。有一个矮角落，一个高角落相反，还有一个明显的对角线高度梯度。

您可以看到空军方法如何在更短的时间内得出结果，如果您不关心完美性。您还可以看到如何有效地实现完美性。您已经知道最矮和最长的人位于两个角落。第二矮的可能在最矮的后面或旁边，第三矮的可能在他后面或旁边。一般来说，某人的身高排名也是他距离矮角落的最大曼哈顿距离。

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

按照这个计划将使用大量CPU，但您将充分利用您的人力资源。