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]

results matching ""