问通用实用的排序算法比O(n log n)快？

EN

许多人提到了比较排序算法的信息论Ω(n lg n)界，这个界在比较排序中是不能被打破的。(This earlier question探讨了为什么会这样。)

然而，有一些类型的比较排序，虽然在平均情况下不会破坏O(n lg n)，但可以证明在某种程度上已经预先排序的输入上运行得更快。例如，Dijkstra的平滑排序在已经排序的输入上以O(n)的速度运行，最坏情况下的行为为O(n lg n)。我最喜欢的排序之一，Cartesian tree sort，可以证明在一些指标中利用了预排序的最佳优势。例如，它可以在O(n)时间内对具有固定数量的递增或递减的子序列的任何序列进行排序，在最坏的情况下可以优雅地降级到O(n lg n)。

关于非比较排序，有一些著名但棘手的整数排序算法，它们通过巧妙的位操作技巧超过O(n lg n)。最著名的整数排序算法是随机化算法，排序时间为O(n√lg lg n)，而最快的确定性整数排序算法的时间为O(n lg lg n)。您可能听说过基数排序在O(n)中工作，尽管从技术上讲它是O(n lg U)，其中U是要排序的数组中的最大值。

简而言之，不，你不能比O(n lg n)做得更好，但如果你对你的输入有所了解，你可以做得稍微好一点。

对于只能比较而不能访问其内部的通用元素，排序算法不可能比Theta(n log n)更快。这是因为有n个！(n阶乘)元素的可能顺序，您需要进行Theta(n log n)比较才能区分所有元素。

不是的。这是我们拥有的为数不多的算法的严格最小界限之一。对于n个元素的集合，有n！不同的顺序，所以要指定一个给定的顺序，我们需要log(n!)比特。根据Stirling的近似，这大约是n。对于我们在元素之间进行的每次比较，我们基本上得到了一位信息(忽略元素相等的可能性)。