基数排序

本页面将简要介绍基数排序。

定义

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。

过程

基数排序的工作原理是将待排序的元素拆分为 个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 关键字进行稳定排序，再对第 关键字进行稳定排序，再对第 关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

基数排序需要借助一种 稳定算法 完成内层对关键字的排序。

通常而言，基数排序比基于比较的排序算法（比如快速排序）要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择。¹

基数排序的正确性可以参考 《算法导论（第三版）》第 8.3-3 题的解法 或自行理解。

性质

稳定性

基数排序是一种稳定的排序算法。

时间复杂度

一般来说，如果每个关键字的值域都不大，就可以使用

计数排序 作为内层排序，此时的复杂度为 ，其中 为第 关键字的值域大小。如果关键字值域很大，就可以直接使用基于比较的 排序而无需使用基数排序了。

空间复杂度

基数排序的空间复杂度为 。

算法实现

伪代码

C++

实际上并非必须从后往前枚举才是稳定排序，只需对 cnt 数组进行等价于 std::exclusive_scan 的操作即可。

参考资料与注释

Footnotes

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms(3rd ed.). MIT Press and McGraw-Hill, 2009. ISBN 978-0-262-03384-8. "8.3 Radix sort", pp. 199. ↩