是否有可能以線性時間排序整數數組？

Question

有一天，我正在閱讀有關谷歌和微軟實習的訪談博客，我讀到其中一個問題是如何在線性時間內排列整數。

我認爲排序東西的最佳方式是O（n日誌（n））像Mergesort或Quicksort，但知道我不確定。有什麼想法嗎？

Answer 1

那麼，這個問題一定會有更多的限制。例如，如果數組僅包含幾個重複數字[1 3 2 6 3 1 2]，則可以使用counting sort在線性時間內完成此操作，但會佔用更多空間。

另一種算法是Dutch National Flag算法，它可以在線性時間內對3個重複數進行排序。除此之外，我不認爲（無知在這裏不是幸福：P）我知道在線性時間對正常數組進行排序的方法。

即使你使用Radix sort它會佔用O(m * n)但如果m <<< n你可以爭辯說，它大約O(n)

Answer 2

O(n lg n)是你能爲基於比較-排序，不要求你做的最好知道你正在排序的項目的任何內容，而不是你如何比較一個到另一個。對有界大小的整數列表進行排序（即每個整數至多爲K，其中K獨立於n）是一個更加專門的問題，因此您可以使用運行速度比O(n lg n)（例如基數排序）更快的更專用的算法， 。