什麼時候可以使用基數排序？

Question

對您的數據有什麼限制可以使用基數排序？

如果我正在整理一個大整數列表，是否適合使用基數排序？爲什麼基數排序不被使用更多？

Answer 1

當你擁有一大組數據並且鍵受到某種限制時，這很好。例如，當您需要訂購一百萬個64位數字的數組時，可以使用它排序8個最低有效位，然後8個等等（應用8次）。這樣這個數組可以在8 * 1M操作中排序，而不是1M * log（1M）。

Answer 2

如果你知道的整數值的範圍，這不是太大，
也許counting sort將你的情況是更好的選擇。

Answer 3

你可能不會像你想象的那樣經常看到它的一個原因是基數排序不像基於比較的排序（quicksort/mergesort/heapsort）那樣具有通用性。它要求您可以將要排序的項目表示爲整數或類似整數的項目。使用標準庫時，很容易定義比較任意對象的比較函數。定義一種將您的任意數據類型正確映射爲整數的編碼可能會更困難。

Answer 4

當離散鍵值的數量相對於數據項的數量較小，並且目標是在不干擾原始數據的情況下產生列表的重新排序副本（因此需要同時維護列表的新舊版本不是一種負擔）。如果可能的密鑰數量太大而無法在一次傳遞中處理，則可以通過多次傳遞將桶類型擴展爲基數排序，但是失去了桶類型可以爲小型密鑰提供的速度優勢。

在一些外部排序情況下，特別是當不同鍵值的數量非常小（例如兩個）時，需要穩定的排序，並且I/O設備只能用一個順序數據流高效地運行，可能對K通過源數據流有用，其中K是鍵值的數量。在第一遍中，複製鑰匙爲最小合法值的所有物品，並跳過其餘部分，然後複製鑰匙位於下一個較高值的所有物品，跳過其餘部分，等等。這種方法顯然效率非常高如果有很多不同的關鍵值，但是如果有兩個關鍵值則會很好。