基数排序

基数排序的时间复杂度是${\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}$ 。

如果考虑和比较排序进行对照，基数排序的形式复杂度虽然不一定更小，但由于不进行比较，因此其基本操作的代价较小，而且在适当选择的${\displaystyle B}$ 之下，${\displaystyle k}$ 一般不大于${\displaystyle \log n}$ ，所以基数排序一般要快过基于比较的排序，比如快速排序。