對任意長度的二進制字符串進行基數排序

我搜索了一下，看到關於二進制字符串基數排序的大量討論，但它們都有相同的長度，如何使用任意長度的aobut二進制字符串？對任意長度的二進制字符串進行基數排序

說我有{「001」，「10101」，「011010」，「10」，「111」}，我如何對它們進行基數排序？謝謝！

來源

2010-01-31 ohana

查找最大長度並將它們全部填充到該長度。如果長度最長的字符串的長度有一些上限，應該仍然表現良好。

來源

2010-01-31 03:14:39

原則上相同的事情，但...將字符串轉換爲整數？ – Steve314 2010-01-31 03:17:41

您可以將它們全部填充爲相同的長度，但是沒有真正的理由運行排序算法來確定二進制中的長度5數大於長度2。通過按長度對數字進行分組並在每個組內運行基數排序，您可能會獲得更好的性能。當然，這取決於你如何對他們進行分組，然後依據你如何分類你的組。

如何做到這一點的一個例子是運行所有的項目一次，並將它們全部扔到一個哈希表（長度 - >該數字的長度）。這需要線性時間，然後讓我們說nlogn時間來按順序訪問它們。基數排序以O（nk）時間運行，其中n是項目的數量，k是它們的平均長度。如果你有一個很大的k，那麼O（nk）和O（nlogn）之間的差異是可以接受的。

來源

2010-01-31 03:27:58 karenc

不錯，但... 不會重新分組它們需要預排序操作來將所有字符串排序到合適的組中嗎？ – FrustratedWithFormsDesigner 2010-01-31 03:31:03

是的，對於小k來說可能不值得。基數排序是一種「線性」時間排序算法，如果您假設k是一個常數或至少很小。但是對於大K而言，預分類將是值得的。預先排序的方式可能比我上面提到的要好，但這是想到的第一個合理的方式。 – karenc 2010-01-31 03:35:42

-1

如果創建大量新的字符串實例會留下令人厭惡的味道，請自行編寫比較。

比較什麼字符串的長度將沒有前導0（即找到firstIndexOf("1")）;較長的字符串較大。
如果二者的長度相同，則繼續逐字比較它們，直到找到兩個不同的字符 - 帶有「1」的字符串較大。

來源

2010-01-31 03:36:18

不知道爲什麼downvote：用一個新的字符串替換每個字符串（按照最高票數的答案）將使算法所需的內存增加一倍以上，這在很多情況下很可能是一個問題。 – 2011-01-30 02:06:48

對任意長度的二進制字符串進行基數排序

回答

相關問題