一尘不染

有没有比Bogosort(aka Monkey Sort)更糟糕的排序算法?[关闭]

algorithm

我的同事带我回到了大学时代,今天早上讨论了排序算法。我们回想起了我们最喜欢的StupidSort,例如其中之一,我们确定我们看到的排序算法是O(n!)。这使我开始寻找可以找到的“最差”的排序算法。

我们假设完全随机的排序会很糟糕(即将元素随机化-是否按顺序排序?否?再次随机化),我环顾四周,发现它显然叫做BogoSort或Monkey
Sort,有时甚至是Random Sort

Monkey Sort似乎具有的最差情况性能O(∞),的最佳情况性能O(n)和平均性能O(n·n!)

目前平均可接受的排序性能最差的排序算法是什么(并且比差O(n·n!))?


阅读 507

收藏
2020-07-28

共1个答案

一尘不染

摘自David Morgan-Mar的 “深奥算法”页面:
智能设计排序

介绍

智能设计排序是一种基于智能设计理论的排序算法。

算法说明

原始输入列表按其确切顺序的概率为1
/(n!)。这种可能性很小,以至于说这是偶然发生显然是荒谬的,所以它一定是由智能分拣机有意识地按顺序排列的。因此可以肯定地说,它已经以某种超越了我们对“升序”的天真凡俗的理解的最佳方式进行了排序。任何试图改变秩序以符合我们自己的先入之见的尝试实际上都会使它的分类减少。

分析

该算法在时间上是恒定的,并且对列表进行原位排序,根本不需要额外的内存。实际上,它甚至不需要任何可疑的技术计算机内容。赞美分拣机!

反馈

加里·罗杰斯写道:

使排序时间保持不变会拒绝排序器的功能。排序器存在于时间之外,因此排序是永恒的。需要时间来验证排序会削弱排序器的作用。因此…这种特殊的分类是有缺陷的,不能归因于“分类器”。

异端!

2020-07-28