我應該在基數排序中使用哪個基地？我該如何轉換基地？

Question

如果我必須對基數爲10的整數列表進行排序，首先我將這些整數轉換爲基數2，然後執行基數排序並最終將整數轉換回基數10？

一般來說，你如何執行基數不同於列表中整數基數的基數排序？

Answer 1

一般來說，這取決於輸入如何表示。

如果輸入被表示爲固定寬度的整數值，則可以很容易通過使用除法以及mod鹼基之間進行轉換。例如，您可以通過計算n % b來獲取數字n的最後一個b位數字，並可以通過計算n/b（舍入）關閉該數字。

如果你的輸入被表示爲字符串，那麼很難重新解釋其他基地的字符。在不使用花哨的算法技術的情況下，通常可以通過將數字塊視爲單個數字來切換爲基數的基數，其中數字代表基數。您也可以使用較小的基數，例如，取每個數字，分別用較小的基數重寫這些數字，然後使用小於一位的基數排序。

如果你有興趣使用真正重量級的理論技術，this paper demonstrates a way to encode numbers in any base in binary in a way that allows for constant-time random access of the digits with no loss in space。這當然比其他方法更先進，恆定的因素可能會在實踐中造成這種效率低下，但它表明理論上可以使用任何你想要的基礎。