# Radix Sort

經典排序演算法 - 基數排序Radix sort

原理類似桶排序 Bucket Sort,這裡總是需要10個桶,多次使用

首先以個位數的值進行裝桶,即個位數爲1則放入1號桶,爲9則放入9號桶,暫時忽視十位數

例如

取一個簡單的待排序陣列[62,14,59,88,16]

分配10個桶,桶編號爲0-9,以個位數數字爲桶編號依次放入桶,變成下邊這樣

|  0  |  0  | 62 |  0  | 14 |  0  | 16 |  0  |  88 | 59 |

|  0  |  1  |  2  |  3  |  4 |  5  |  6  |  7  |  8  |  9  |桶編號

將桶裏的數字順序取出來,

輸出結果:[62,14,16,88,59]

再次入桶,不過這次以十位數的數字爲準,進入相應的桶,變成下邊這樣:

由於前邊做了個位數的排序,所以當十位數相等時,個位數字是由小到大的順序入桶的,就是說,入完桶還是有序

|  0  | 14,16 |  0  |  0  |  0  | 59 | 62  | 0  | 88  |  0  |

|  0  |  1      |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |桶編號




因爲沒有大過100的數字,沒有百位數,所以到這排序完畢,順序取出即可

最後輸出結果:[14,16,59,62,88]


文章引用自
http://www.cnblogs.com/kkun/archive/2011/11/23/2260275.html
