如何msd減少密鑰的檢查數

Question

我正在閱讀以下鏈接的MSD。

http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

這裏應提到的是在MSD可能沒有檢查第20頁。這是如何與第18頁上的程序時，我試圖通過我把代碼步行的例子上的所有按鍵我無法理解我們如何減少檢查所有的關鍵。

謝謝！

Answer 1

比方說，你有：（0的確實可以是任意）

600000 
100000 
300000 
500000 
400000 
200000 

如果你只在最顯著數字排序，你會得到：

100000 
200000 
300000 
400000 
500000 
600000 

這個數組已經完成排序後我們可以停止 - 不需要檢查其他數字。

雖然它可能不會在實踐中那麼理想，當然也有我們沒有評估所有的所有元素的數字情況。

如果子數組中只有一個元素，if (hi <= lo + 1) return;語句會導致它返回，從而阻止檢查不必要的數據。