软考-软件设计师：排序算法-基数排序 作者：马育民 • 2025-04-15 08:52 • 阅读：10004 # 基数排序 1. 首先确定 **最大的数的位数** 最大数是一位数，即：个位；两位数，即：十位；三位数，即：百位 2. 定义十个桶，编号 `0-9`（这是固定的） 3. 先按照每个数的 **个位数** 排序，放入桶内，得到一个序列，桶清空； 4. 依据上个序列，按照每个数的 **十位数** 排序，放入桶内，得到一个序列，桶清空； 5. 以此类推，直到完成最大数的位数 ### 例子 对序列 `135,242,192,93,345,11,24,19` 进行排序 **首先确定最大的数的位数** **最大的数** 是 `345`，是 **百位数**，**3位数**，也就是说要执行 **3趟** **第1趟** 定义十个桶，编号 `0-9`，按照每个数的 **个位数** 排序，放入桶内，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwroKDfyS.png) 然后展开，桶清空，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwrowErCZ.png) **第2趟** 按照每个数的 **十位数** 排序，放入桶内，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwrqA82Ff.png) 然后展开，桶清空，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwrqmISJl.png) **第3趟** 按照每个数的 **百位数** 排序，放入桶内，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwrtFPnDv.png) 然后展开，桶清空，如下图： [](https://www.malaoshi.top/upload/0/0/1GWwrtcRviz.png) ### 是否稳定 稳定 ### 时间复杂度 约为 `O（d（n+rd))` ### 空间复杂度 在排序过程中仅需要一个元素的辅助空间用于数组元素的交互 空间复杂度为 `O(rd)` 原文出处：http://malaoshi.top/show_1GWwrx8Nmn9.html