我在考慮線性時間排序問題，它出現在相當多的數據源中，這些數據源會提示您在線性時間內對0至n^3-1範圍內的數字進行排序。將線性時間的基數排序與將轉換輸入轉換爲合適的基數
因此，要做到這一點的方法之一是使用通常在O(wn)運行，其中w是通過觀察，我們可以通過使用底座n獲得字長3爲任意數量的該範圍內的最大字長基數排序。
而且這裏存在我的問題 - 雖然它在紙面上看起來正常，實際上將所有的數字立足n用簡單的方式是要採取相當多的時間，很可能比後來的排序本身甚至更多。有沒有什麼辦法可以比天真地快速轉換爲基地n或以某種方式欺騙你的方式擺脫這種限制，或者你只需要忍受它？
一個有用的觀察結果是，如果您選擇的基數不是n，而是大於或等於n的最小冪，則此算法的運行時間相同。我們假設那個數字是2 k。現在，爲了讀取數字的基數，可以檢查數字中大小爲k的比特塊，這可以使用一些比特移位和邏輯與非常快地執行。假設可變長度整數使用了一些很好的二進制編碼，這可能會很快，即使您的數字存儲爲可變長度整數。
有一個理想的大小選擇k位字段使用2 k作爲基數的基數根據數組的大小，但它沒有很大的差異，選擇小於10％因爲r = 8更容易緩存，所以r = 8（1次讀取通過+4次基數排序遍歷），而r = 16（1次讀取通過+ 2次基數排序遍歷）。在我的系統上（Intel 2600K 3.4 ghz），對於數組大小= 2^20，r = 8是最快的。對於數組大小= 2^24，r = 10.67（使用10,11,11位字段）稍快。對於數組大小= 2^26，r = 16是最快的。
對於帶符號整數，符號位可以在基數排序期間切換。
在你的情況下，給出一個整數的最大值，所以這將有助於選擇位字段的大小。