小编典典

有没有比 Bogosort(又名猴子排序)更糟糕的排序算法?

all

今天早上,我的同事们通过讨论排序算法让我回到了大学时代。我们回忆起我们最喜欢的StupidSort,我们中的一个人确信我们已经看到了一种排序算法O(n!)。这让我开始四处寻找我能找到的“最差”的排序算法。

我们假设完全随机排序会非常糟糕(即随机化元素 - 是否按顺序排列?不?再次随机化),我环顾四周,发现它显然被称为BogoSort,或猴子排序,或者有时只是随机排序.

Monkey Sort 的最坏情况性能为O(∞),最佳情况性能为O(n),平均性能为O(n·n!)。

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


阅读 80

收藏
2022-07-09

共1个答案

小编典典

来自David Morgan-Mar的 Esoteric Algorithms 页面:智能设计排序

介绍

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

算法描述

原始输入列表与其所在顺序完全相同的概率是 1/(n!)。这种可能性很小,说这是偶然发生的显然是荒谬的,所以它一定是由智能分拣员有意识地排列的。因此可以安全地假设它已经以某种方式优化排序,超越了我们对“升序”的天真凡人理解。任何试图改变该顺序以符合我们自己的先入之见的尝试实际上都会使它变得不那么有序。

分析

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

反馈

加里·罗杰斯写道:

使排序在时间上保持不变否定了 The Sorter 的功能。Sorter 存在于时间之外,因此排序是永恒的。需要时间来验证排序会削弱排序器的作用。因此......这种特殊的排序是有缺陷的,不能归因于“分拣机”。

Heresy!

2022-07-09