基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机（Tabulation Machine）上的贡献[1]。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
效率
基数排序的时间复杂度是{\displaystyle O(k\cdot n)}，其中{\displaystyle n}是排序元素个数，{\displaystyle k}是数字位数。注意这不是说这个时间复杂度一定优于{\displaystyle O\left(n\cdot \log \left(n\right)\right)}，{\displaystyle k}的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；{\displaystyle k}决定了进行多少轮处理，而{\displaystyle n}是每轮处理的操作数目。
以排序{\displaystyle n}个不同整数来举例，假定这些整数以{\displaystyle B}为底，这样每位数都有{\displaystyle B}个不同的数字，{\displaystyle k=\log _{B}N}，{\displaystyle N}是待排序数据类型全集的势。虽然有{\displaystyle B}个不同的数字，需要{\displaystyle B}个不同的桶，但在每一轮处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理的时候都需要平均{\displaystyle n}次操作来把整数放到合适的桶中去，所以就有：
{\displaystyle k\approx \log _{B}N}
所以，基数排序的平均时间{\displaystyle T}就是：
{\displaystyle T\approx \log _{B}\left(N\right)\cdot n}
其中前一项是一个与输入数据无关的常数，当然该项不一定小于{\displaystyle \log n}。
如果考虑和比较排序(Comparison sort)进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且在适当选择的{\displaystyle B}之下，{\displaystyle k}一般不大于{\displaystyle \log n}，所以基数排序一般要快过基于比较的排序，比如快速排序。
原文地址：https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
在知识共享 署名-相同方式共享 3.0协议之条款下提供
