<分区>
今天早上，我的同事们讨论了排序算法，让我回到了大学时代。我们记忆起我们的最爱，例如 StupidSort ，我们中的一个人确信我们看到了一种 O(n!) 的排序算法。这让我开始四处寻找我能找到的“最差”排序算法。
我们假设完全随机排序会很糟糕(即随机化元素 - 它是有序的吗？不？再次随机化)，我环顾四周，发现它显然被称为 BogoSort, or Monkey Sort, or sometimes just Random Sort .
Monkey Sort 似乎具有 O(∞) 的最坏情况性能，O(n) 的最佳情况性能，以及 的平均性能O(n·n!).
目前官方认可的平均排序性能最差(甚至比O(n·n!))的排序算法是什么？
最佳答案
来自 David Morgan-Mar的深奥算法页面: Intelligent Design Sort
Introduction
Intelligent design sort is a sorting algorithm based on the theory of intelligent design.
Algorithm Description
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.
Analysis
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!
Feedback
Gary Rogers writes:
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 diminishes the role of the Sorter. Thus... this particular sort is flawed, and can not be attributed to 'The Sorter'.
异端邪说!
关于algorithm - 有没有比 Bogosort(又名猴子排序)更糟糕的排序算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2609857/