最好的運行時間來訂購n號碼

Question

我有0和（n^4 - 1）之間的n個數字我可以對它們進行排序的最快方式是什麼。

當然，nlogn是微不足道的，但我想到基數n的基數排序的選項，而不是線性時間，但我不確定，因爲-1。

感謝您的幫助！

Answer 1

我認爲你誤解了基數排序的效率。從Wikipedia：

基數的排序複雜度爲O（WN）爲n鍵是整數的字大小爲w。有時w表示爲一個常數，這會使基數排序比基於比較的最佳排序算法更好（對於足夠大的n），排序算法都執行O（n log n）比較來對n個鍵進行排序。然而，通常w不能被認爲是一個常數：如果所有n個密鑰都不相同，那麼對於一個隨機訪問機器而言，w必須至少記錄n，以便能夠將它們存儲在存儲器中，這至少給出時間複雜度O （n log n）。

我個人會選擇intelligent pivot來實現快速排序。使用這種方法可以達到約1.188 n log n的效率。

Answer 2

如果我們使用基數n中的基數排序，我們可以得到期望的線性時間複雜度，-1無關緊要。

我們將代表n爲底的數字：

然後我們得到：< =（日誌（n爲底）（N^4 - 1））*（N + N）< = 4 *（2N ）< = O（n）。

n代表n個數字，另一個n代表數字跨度（高估），n^4 - 1的對數小於log n^4，在基數n中爲4。整體線性時間複雜度。

感謝您的幫助！如果我做錯了，請通知我！