原文連結
基數排序和計數排序一樣無需進行比較和交換，和桶排序一樣利用分布和收集兩種基本操作進行排序。基數排序是把每一個元素拆成多個關鍵字，一個關鍵字可以在每一個元素上同等的位置進行計數排序，一個元素拆成多個關鍵字可以看作是要進行幾輪分桶，以一個元素最長的長度為準。
基數排序可以看成多（單）關鍵字的排序，可以想象成桶排序那樣分桶排序，也可以像計數排序那樣歸約化分治。
基數排序的思想是将待排序序列中的每組關鍵字進行桶排序。例如整數序列[103, 9, 1,7,11,15, 25, 201, 209, 107, 5]上每個位、十位和百位上的數字看成是一個關鍵字。
基數排序有兩種方式進行，一種是LSD，從右邊關鍵字開始排序，另一種是MSD，從左邊關鍵字開始排序。
基數排序LSD
我們将輸入數組[103, 9, 1,7,11,15, 25, 201, 209, 107, 5]，從右邊關鍵字開始，以個位數上開始分桶，對于數字，每一個關鍵字取值範圍是0~9，最多需要10個桶。如果是字元，按ASCII碼最多需要128個桶，看情況而定。
為了保證元素之間的穩定性，就按計數排序一樣，将給出一個統計數組c，長度為10，統計輸入數組每一個元素對應的關鍵字。然後從統計數組c第2個位置開始，進行目前一項和前一項的累加。累加完之後反向填充數組b，也将數組b直接複制到數組array。
再進行循環操作exp*=10，以十位數上進行分桶，直到超過某個元素的最長長度。
動畫：LSD
Code
Result
初始狀态 [103, 9, 1, 7, 15, 25, 109, 209, 5]
計數c [0, 1, 0, 1, 0, 3, 0, 1, 0, 3]
計數求和c [0, 1, 1, 2, 2, 5, 5, 6, 6, 9]
......
b [1, 103, 15, 25, 5, 7, 9, 109, 209]
計數c [7, 1, 1, 0, 0, 0, 0, 0, 0, 0]
計數求和c [7, 8, 9, 9, 9, 9, 9, 9, 9, 9]
……
b [1, 103, 5, 7, 9, 109, 209, 15, 25]
計數c [6, 2, 1, 0, 0, 0, 0, 0, 0, 0]
計數求和c [6, 8, 9, 9, 9, 9, 9, 9, 9, 9]
b [1, 5, 7, 9, 15, 25, 103, 109, 209]
[1, 5, 7, 9, 15, 25, 103, 109, 209]
基數排序MSD
基于MSD方式的基數排序不能像LSD方式循環操作，它是将大問題分解成小問題進行基數排序的。
如果輸入數組[103, 9, 1,7,11,15, 25, 201, 209, 107, 5]，從左邊關鍵字開始，以百位數上開始分桶，進行完一次計數排序之後可以看到上面輸出的數組b[9, 1, 7, 15, 25, 5, 103, 109, 209]，如果還是按照前面的步驟分桶和計數排序，這組數組就已被打亂了，103、109和209這三個數在十位上為0，是最小的，不符合基數排序。
最好的方式是将大問題分解成一個個可以解決符合基數排序的小問題。上一次按百位數上開始分桶之後，還要将折回之前的數組c統計累加的過程。
設定數組array的low和high的位置，值可以擷取折回統計累加之後的數組c上對應的值。數組array中[9, 1, 7, 15, 25, 5], [103, 109], [209]的長度和統計數組c上的[6, 2, 1]剛好對應，是以當進行遞歸方式的時候low和high上的值可以從數組c中擷取，exp上的指數也對應的除以10，遞歸終止條件正是exp <= 0。
動畫：MSD
統計c [6, 2, 1, 0, 0, 0, 0, 0, 0, 0]
求和統計c [6, 8, 9, 9, 9, 9, 9, 9, 9, 9]
b [9, 1, 7, 15, 25, 5, 103, 109, 209]
遞歸
統計c [4, 1, 1, 0, 0, 0, 0, 0, 0, 0]
求和統計c [4, 5, 6, 6, 6, 6, 6, 6, 6, 6]
b [9, 1, 7, 5, 15, 25]
統計c [0, 1, 0, 0, 0, 1, 0, 1, 0, 1]
求和統計c [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
b [1, 5, 7, 9]
來源 | 算法無遺策
作者 | 我脫下短袖