查看“︁基数排序”︁的源代码

{{Request translation}}
{{NoteTA
|G1 = IT
}}
{{Infobox Algorithm
|class=[[排序算法]]
|image=基数排序.gif
|data=[[数组]]
|time=<math>O(kN)</math>
|space=<math>O(k+N)</math>
|optimal=Yes
}} 
'''基数排序'''（{{lang-en|Radix sort}}）是一种非比较型[[整数]][[排序算法]]，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

== 歷史 ==
基数排序的发明可以追溯到1887年[[赫尔曼·何乐礼]]在{{tsl|en|Tabulation Machine|打孔卡片製表機}}上的贡献<ref>{{Cite patent|US|395781}}和{{Cite patent|UK|327}}</ref>。基數排序演算法早在1923年被廣泛運用在[[打孔卡]]的排序<ref name="auto">
[[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0}}. Section 5.2.5: Sorting by Distribution, pp.&nbsp;168–179.
</ref>。

==效率==

基数排序的时间复杂度是<math>O(k\cdot n)</math>，其中<math>n</math>是排序元素个数，<math>k</math>是数字位数。注意这不是说这个时间复杂度一定优于<math>O\left(n\cdot\log\left(n\right)\right)</math>，<math>k</math>的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；<math>k</math>决定了进行多少轮处理，而<math>n</math>是每轮处理的操作数目。

以排序<math>n</math>个不同整数来举例，假定这些整数以<math>B</math>为底，这样每位数都有<math>B</math>个不同的数字，<math>k=\log_B N</math>，<math>N</math>是待排序数据类型全集的势。虽然有<math>B</math>个不同的数字，需要<math>B</math>个不同的桶，但在每一轮处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理的时候都需要平均<math>n</math>次操作来把整数放到合适的桶中去，所以就有：
: <math>k\approx\log_B N</math>

所以，基数排序的平均时间<math>T</math>就是：
: <math>T\approx\log_B\left(N\right)\cdot n</math>

其中前一项是一个与输入数据无关的常数，当然该项不一定小于<math>\log n</math>。

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

==参考文献==
{{reflist}}

==外部連結==
{{wikibook|算法实现/排序/基数排序}}

{{排序算法表}}
[[Category:排序算法]]

[[no:Sorteringsalgoritme#Radix-sortering]]