通用實用的排序算法比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。對於我們在元素之間進行的每一次比較，我們基本上得到了一點信息（忽略了相同元素的可能性）。