基数排序
基数排序（Radix Sort）是一种非比较型整数排序算法，它通过将整数按位数切割成不同的数字，然后按每个位数分别进行比较和排序。基数排序的核心思想是“分配”和“收集”，它适用于整数或字符串的排序。
基数排序的工作原理
基数排序的基本思想是从最低位（个位）开始，依次对每一位进行排序。每次排序时，将数字分配到对应的“桶”中，然后再按顺序收集起来。这个过程会重复进行，直到最高位排序完成。
基数排序的时间复杂度为 O(nk)，其中 n 是待排序元素的数量，k 是数字的最大位数。基数排序的效率取决于数字的位数，因此它特别适合处理位数较少的整数。
基数排序的步骤
- 初始化：确定待排序数组中最大数字的位数
k。 - 按位排序：从最低位（个位）开始，依次对每一位进行排序：
- 将数字分配到对应的桶中（0-9）。
- 按顺序收集桶中的数字。
- 重复：重复上述步骤，直到最高位排序完成。
- 完成：最终数组即为排序后的结果。
基数排序的代码示例
以下是一个基数排序的 Python 实现：
python
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# 统计每个桶中的元素数量
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
# 计算累加值，确定每个桶的结束位置
for i in range(1, 10):
count[i] += count[i - 1]
# 将元素放入输出数组
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# 将排序后的结果复制回原数组
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
# 找到数组中的最大值
max_num = max(arr)
# 从最低位开始，依次对每一位进行排序
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
# 示例
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("排序后的数组:", arr)
输入：[170, 45, 75, 90, 802, 24, 2, 66]
输出：[2, 24, 45, 66, 75, 90, 170, 802]
备注
基数排序的关键在于每次只对一位进行排序，因此它需要多次遍历数组。每次遍历的时间复杂度为 O(n)，总时间复杂度为 O(nk)。
基数排序的实际应用场景
基数排序在以下场景中非常有用：
- 整数排序：当需要排序的整数范围较小且位数较少时，基数排序的效率非常高。
- 字符串排序：基数排序也可以用于按字典序排序字符串，每个字符可以看作是一个“位”。
- 大数据处理：在处理大规模数据时，基数排序的稳定性和线性时间复杂度使其成为理想选择。
实际案例：电话号码排序
假设我们需要对一组电话号码进行排序，每个电话号码由 10 位数字组成。基数排序可以按从最低位到最高位的顺序依次对每一位进行排序，最终得到按字典序排列的电话号码列表。
总结
基数排序是一种高效的整数排序算法，特别适合处理位数较少的整数或字符串。它的核心思想是通过多次分配和收集操作，按位对数字进行排序。虽然基数排序的时间复杂度为 O(nk)，但在实际应用中，它的性能通常优于其他比较型排序算法。
提示
如果你对基数排序感兴趣，可以尝试以下练习：
- 修改代码，使其支持负数的排序。
- 尝试用基数排序对一组字符串进行排序。
- 比较基数排序与其他排序算法（如快速排序、归并排序）的性能差异。
希望这篇内容能帮助你更好地理解基数排序！如果你有任何问题，欢迎在评论区留言。