今天早上,我的同事讨论了排序算法,把我带回了大学时代。我们回忆起我们的最爱,比如愚蠢的排序,我们中的一个人确信我们见过O(n!)
的排序算法。这让我开始四处寻找我能找到的“最糟糕”的排序算法。
我们假设完全随机的排序将是非常糟糕的(即,随机化元素-它是有序的吗?没有?再次随机化),我环顾四周,发现它显然被称为BogoSort,或猴子排序,或有时只是随机排序。
猴子排序似乎具有O(∞)
的最坏情况性能、O(n)
的最好情况性能和O(n·n!)
的平均性能。
目前官方公认的平均排序性能最差(甚至比O(n·n!)
还差)的排序算法是什么?