是否有可用的排序算法，其時間複雜度爲O（N）？

Question

大多數排序算法的複雜度爲O（N N）或O（N logN）以獲得結果。但是，對於特定的一組輸入，存在具有O（N）的複雜度的算法。想知道是否有可用的排序算法，在所有情況下都具有O（N）的複雜度。

Answer 1

如果只能比較（檢查兩個項目是否爲<，>，==），那麼排序的值就不會比O（n log（n））做得更好。它是那裏算法的幾個經證實的下界之一。證明不是太複雜（查看維基百科上的比較排序以瞭解詳細信息），但足夠長時間不在這裏重複。

如果您可以做比較之外的事情，那麼您可以擁有更多的靈活性。如果你有數字，你可以檢查桶排序（一種基數排序），它可以使O（n）排序成爲可能。

Answer 2

不是。最快的通用排序算法都是O（nlgn）。實際上Θ（nlgn），因爲它已經在數學上證明基於比較的排序算法不會更有效。

這裏是我在基於比較的排序算法中找到的一篇論文，它解釋了它。 http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

Answer 3

簡短的回答是否定的。

如果輸入數組的每個元素都屬於一個有限集合，那麼O（N）算法是可能的。假設輸入總是在有限集[0..9]內。然後你可以創建一個大小爲10的數組，掃描數組並增加相應的索引。

所以，在所有情況下，O（N）排序算法只有在內存無限時纔可能。