基数排序（Radix Sort）是一种非比较型的整数排序算法，它的核心思想是按照数字的每一位（从最低位到最高位，例如个位、十位、百位等）依次进行排序。与基于比较的排序算法（如快速排序、归并排序）不同，基数排序通过“分桶”和“收集”的方式实现排序，特别适合处理整数排序问题。
基数排序的基本思路¶
要使用基数排序，我们需要先确定待排序数组中最大数的位数，例如数组中的最大数是802，它有3位（个位、十位、百位），那么我们就需要对这3位分别进行排序。具体步骤如下：
- 确定位数：找到数组中的最大数，计算其位数（例如802的位数是3）。
- 按位排序：从最低位（个位，第0位）开始，依次到最高位（百位，第2位）。对于每一位，我们将数组中的元素按照当前位的数字分到不同的“桶”中，然后按顺序收集这些桶中的元素，完成该位的排序。
- 重复处理：对每一位重复上述分桶和收集操作，直到所有位都处理完毕，数组即完成排序。
Python实现步骤¶
下面我们通过代码实现基数排序，关键步骤如下：
def radix_sort(arr):
# 处理空数组情况
if not arr:
return arr
# 找到数组中的最大数，确定需要排序的位数
max_num = max(arr)
digits = len(str(max_num)) # 最大数的位数，例如max_num=802时，digits=3
# 遍历每一位（从最低位到最高位，digit从0开始）
for digit in range(digits):
# 初始化10个桶（0-9），每个桶用于存放当前位数字相同的元素
buckets = [[] for _ in range(10)]
# 按当前位的数字将元素分到对应的桶中
for num in arr:
# 获取当前位的数字：(num // 10^digit) % 10
current_digit = (num // (10 ** digit)) % 10
buckets[current_digit].append(num)
# 将所有桶中的元素按顺序收集，更新数组为当前位排序后的结果
arr = []
for bucket in buckets:
arr.extend(bucket)
return arr
代码解释¶
- 处理空数组：如果输入数组为空，直接返回空数组，避免后续计算错误。
- 确定位数：通过
max(arr)找到最大数，再用len(str(max_num))计算其位数（例如802的位数是3）。 - 分桶与收集：
- 初始化桶：创建10个空列表（对应0-9的数字），用于存放每一位排序后的元素。
- 按位分桶：遍历数组中的每个数，通过(num // (10 ** digit)) % 10获取当前位数字（例如170的第0位（个位）是170//1 %10=0，第1位（十位）是170//10 %10=7），并将数放入对应桶中。
- 收集元素：将所有桶中的元素按顺序连接，得到当前位排序后的数组，作为下一位排序的输入。
测试示例¶
以数组[170, 45, 75, 90, 802, 24, 2, 66]为例验证算法：
1. 处理个位（第0位）：所有数的个位数字为0,5,5,0,2,2,4,6，分桶后收集结果为[170, 90, 802, 2, 24, 45, 75, 66]。
2. 处理十位（第1位）：所有数的十位数字为7,9,0,0,2,4,7,6，分桶后收集结果为[802, 2, 24, 45, 66, 170, 75, 90]。
3. 处理百位（第2位）：所有数的百位数字为8,0,0,0,0,1,0,0，分桶后收集结果为[2, 24, 45, 66, 75, 90, 170, 802]，排序完成。
总结¶
基数排序通过按位分桶和收集实现排序，时间复杂度为O(d×(n+k))（其中d是最大数的位数，n是数组长度，k是桶的数量，此处k=10），空间复杂度为O(n+k)。它特别适合处理位数较少的整数数组，尤其当数组中存在重复数字时效率更高。如果需要处理负数，可先将负数转为正数，排序后再恢复符号。