通用实用的排序算法比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）做得更好，但是如果你知道一些关于你的输入的信息，你可以稍微做的更好一些。

Answer 2

对于只能比较而不访问内部元素的通用元素，不可能有比Theta（n log n）更快的排序算法。那是因为有n！ （n阶乘）元素的可能顺序，并且您需要Theta（n log n）比较来区分所有元素。

Answer 3

有多少元素？尽管它类似于N ^1.2，但Shell-Metzner排序通常比其他多数其他元素（几千个元素）要快。

这也取决于你的意思是“通用”和“实用”。基数排序可以击败O（n log n），并且它适用于相当广泛的各种数据（但绝对不是所有的）。

如果你的想法是实用的和通用的，将算法限制为直接比较元素的算法，那么无 - 无（或永远不会）比O（n log n）更好。这已经证明了相当长的一段时间。

Answer 4

不是。这是我们拥有的少数几个严格的最小界限之一。对于n个元素的集合，有n！不同的顺序，所以要指定一个给定的顺序，我们需要log（n！）位。通过斯特林近似，这大约是n log n。对于我们在元素之间进行的每一次比较，我们基本上得到了一点信息（忽略了相同元素的可能性）。