{{Translated page}}
基数排序(英語:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片製表機(英语:Tabulation Machine)上的贡献[1]。基數排序演算法早在1923年被廣泛運用在打孔卡的排序[2]。
基数排序的时间复杂度是 O ( k ⋅ ⋅ --> n ) {\displaystyle O(k\cdot n)} ,其中 n {\displaystyle n} 是排序元素个数, k {\displaystyle k} 是数字位数。注意这不是说这个时间复杂度一定优于 O ( n ⋅ ⋅ --> log --> ( n ) ) {\displaystyle O\left(n\cdot \log \left(n\right)\right)} , k {\displaystyle k} 的大小取决于数字位的选择(比如比特位数),和待排序数据所属数据类型的全集的大小; k {\displaystyle k} 决定了进行多少轮处理,而 n {\displaystyle n} 是每轮处理的操作数目。
以排序 n {\displaystyle n} 个不同整数来举例,假定这些整数以 B {\displaystyle B} 为底,这样每位数都有 B {\displaystyle B} 个不同的数字, k = log B --> N {\displaystyle k=\log _{B}N} , N {\displaystyle N} 是待排序数据类型全集的势。虽然有 B {\displaystyle B} 个不同的数字,需要 B {\displaystyle B} 个不同的桶,但在每一轮处理中,判断每个待排序数据项只需要一次计算确定对应数位的值,因此在每一轮处理的时候都需要平均 n {\displaystyle n} 次操作来把整数放到合适的桶中去,所以就有:
所以,基数排序的平均时间 T {\displaystyle T} 就是:
其中前一项是一个与输入数据无关的常数,当然该项不一定小于 log --> n {\displaystyle \log n} 。
如果考虑和比较排序进行对照,基数排序的形式复杂度虽然不一定更小,但由于不进行比较,因此其基本操作的代价较小,而且在适当选择的 B {\displaystyle B} 之下, k {\displaystyle k} 一般不大于 log --> n {\displaystyle \log n} ,所以基数排序一般要快过基于比较的排序,比如快速排序。