algorithm - 比 O(n log n) 更快的通用且实用的排序算法？

Question

是否有运行速度超过 O(n log n) 的通用元素实用算法(不同于计数排序或桶排序)？

Answer 1

很多人都提到了比较排序算法的信息论 Ω(n lg n) 约束，在比较排序中无法打破。 (This earlier question 探讨了为什么会这样。)

但是，有些类型的比较排序虽然在一般情况下不会破坏 O(n lg n)，但可以证明在已经在某种程度上预排序的输入上运行得更快。例如，Dijkstra 的 smoothsort 在 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) 做得更好，但如果你对输入有所了解，你可以做得更好。