有没有什么更糟糕的排序算法比BOGO排序（又名猴排序）？ [英] Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)?

问题描述

我的同事带我回来的时间到我的大学天，今天上午排序算法的讨论。我们回忆起我们的最爱，如 StupidSort 和我们的人知道我们已经看到了一种算法，该算法是 O（N！）。这让我开始四处寻找最差的排序算法我能找到。

My co-workers took me back in time to my University days with a discussion of sorting algorithms this morning. We reminisced about our favorites like StupidSort, and one of us was sure we had seen a sort algorithm that was O(n!). That got me started looking around for the "worst" sorting algorithms I could find.

我们假定完全随机的排序将是pretty的差（即随机元素 - ？是为了不再次随机化），和我环顾四周，发现，它显然是所谓的BogoSort，或猴子排序，或有时只是随机排序。

We postulated that a completely random sort would be pretty bad (i.e. randomize the elements - is it in order? no? randomize again), and I looked around and found out that it's apparently called BogoSort, or Monkey Sort, or sometimes just Random Sort.

猴子排序看上去有的最坏情况下的性能O（∞）的最佳情况下的性能 O（N）和 O（N·N！）。

Monkey Sort appears to have a worst case performance of O(∞), a best case performance of O(n), and an average performance of O(n·n!).

是否有更差的平均性能比 0任何指定的算法（N·N！）？还是只是比猴子愚蠢的排序有什么看法？

Are there any named algorithms that have worse average performance than O(n·n!)? Or are just sillier than Monkey Sort in general?

推荐答案

从大卫摩根月的神秘算法页 智能设计排序

From David Morgan-Mar's Esoteric Algorithms page: Intelligent Design Sort

简介

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

Intelligent design sort is a sorting algorithm based on the theory of intelligent design.

算法描述

原始输入列表的概率的确切顺序被   它在1 /（N！）。有这样一个小的可能性本，它的   显然荒谬地说，这种偶然发生的，因此它必须有   已经自觉地把以该顺序由一个智能分拣机。因此   它是安全的假设，它已经优化排序以某种方式   超越我们的天真致命的升序的理解。   任何试图改变以符合我们自己的preconceptions   实际上使其不太有序

The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally Sorted in some way that transcends our naïve mortal understanding of "ascending order". Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.

分析

本算法是在时间上恒定的，并分类就地列表中，   无需额外的记忆都没有。实际上，它不连   不需要任何的可疑技术的电脑的东西。赞美   分拣机！

This algorithm is constant in time, and sorts the list in-place, requiring no additional memory at all. In fact, it doesn't even require any of that suspicious technological computer stuff. Praise the Sorter!

反馈

加里·罗杰斯写道：

制作的那种恒定时间     否认的分拣机的电源。该     分拣机的存在以外的时间，从而     排序是永恒的。要需要时间     验证排序dimishes的作用     的分拣机。因此...这个特别的     排序是有缺陷的，并且不能     归因于'分拣机。

Making the sort constant in time denies the power of The Sorter. The Sorter exists outside of time, thus the sort is timeless. To require time to validate the sort dimishes the role of the Sorter. Thus... this particular sort is flawed, and can not be attributed to 'The Sorter'.

异端！

这篇关于有没有什么更糟糕的排序算法比BOGO排序（又名猴排序）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！