基数排序基本信息

Radix Sort 是基于下限比较的算法。它是一种非比较整数排序算法，它通过按键分组键来对整数键进行排序，这些数字共享一些重要的位置和值。基数排序是一种线性时间排序算法，当元素在 1 到 k 的范围内时，它在 O（n + k）时间内排序。Radix Sort 的想法是从最低有效数字到最高有效数字进行逐位数字排序。基数排序使用计数排序作为子程序进行排序。基数排序是桶排序的概括。

Bucket 排序的伪代码：

1. 创建[0..n-1]元素的数组。
2. Call Bucket 重复排序，每个元素的最重要数字至少作为关键字。
3. 返回已排序的数组。

基数排序示例：

http://i.stack.imgur.com/o3im8.jpg

空间辅助： O(n)
时间复杂度： O(n)