排序使用基數排序

Question

我讀從this siteradix sort我感到困惑的第三for loop：

for (i = n - 1; i >= 0; i--) { 
    output[freq[(arr[i]/place) % range] - 1] = arr[i]; 
    freq[(arr[i]/place) % range]--; 
} 

爲什麼他們從結束，當我試圖從0開始就啓動它，它給我的錯誤的答案？任何解釋或解決方案，將不勝感激。

Answer 1

因爲freq包含範圍中每個位置的元素的累積數量。也就是說，對於i = 0-9的範圍，freq[i]包含放置在位置0, ..., i上的位數。

算法使用freq來跟蹤每個位置需要從初始陣列到輸出陣列繪製多少個項目。

假設10,21,17,34,44,11,654,123作爲輸入，運行數排序爲第一個微不足道的數字：

0: 10 
1: 21 11 
2: 
3: 123 
4: 34 44 654 
5: 
6: 
7: 17 
8: 
9: 

freq將如下：

0: 1 
1: 3 
2: 3 
3: 4 
4: 7 
5: 7 
6: 7 
7: 8 
8: 8 
9: 8 

因此，數組變成10,21,11,123,34,44,654,17。

因爲freq是如何構建的，所以您需要向後循環以保留原始的數字順序。假設你想把34放在輸出的正確位置。根據freq數組，如果向前循環，則會將其放在第7個不正確的位置。如果你向後循環，你已經放置了654和44之前達到34，所以freq[4]=5那麼這是正確的地方。