在1到100的情況下以90％的效率高效排序

-4

給定10000個整數的數組，其中90％在1到100之間，其他的在101和10000之間，如何有效地進行排序？在1到100的情況下以90％的效率高效排序

2016-03-24 Qin Lin

傳統算法如quicksort或合併排序有什麼問題？ –

@GordonLinoff Quicksort在基於比較的排序上具有* Ω（n log（n））*下限，而問題表明大多數元素可以使用不具有此下限的計數排序進行排序。所以，原則上，它可以比計算排序更快（這是否會在實踐中發生是另一回事）。 –

@AmiTavory「原則上，它可以比計數排序更快」：如何？ –

元素數量N等於它們的範圍（1到N），因此在整個範圍內使用計數排序是無害的。這是Θ(N)。

2016-03-24 13:53:01

回答