基数排序
基数排序(radix sort)又称桶排序（bucketsort），相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。我在上一篇讲到的计数排序也属于这种排序模式，上一篇结尾处提到了计数排序的稳定性，即排序前和排序后相同的数字相对位置保持不变。今天我们要说的基数排序就要利用到排序稳定性这一点。
排序过程
初始数组：[ 2, 88, 1, 8, 7, 38, 28, 72, 76, 0 ]
1.按个位排序（二维数组bucket空间没用完，就不画全了）
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 72 | 76 | 88 | |||||
| 8 | |||||||||
| 38 | |||||||||
| 28 |
覆盖原数组为：[ 0,1,72,76,88,8,38,28 ]
2.按百位排序(根据覆盖后的数组)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 28 | 38 | 72 | 88 | |||||
| 1 | 76 | ||||||||
| 8 | |||||||||
再次覆盖原数组(最终顺序)：[ 0,1,8,28,38,72,76,88 ]