基数排序（Radix Sort）是一种非比较性排序算法，适用于对整数或字符串等数据进行排序。它根据数据的位数进行排序，从低位到高位或从高位到低位，通过分配数据到不同的桶中，然后按顺序合并这些桶，得到有序数组。基数排序是一种稳定的排序算法，适用于整数或字符串排序。本文将详细介绍基数排序的工作原理和Python实现。
基数排序的工作原理
基数排序的基本思想是：
- 根据数据的位数，从低位到高位或从高位到低位，依次对数据进行排序。
- 每一轮排序根据位数的不同，将数据分配到不同的桶中。
- 按照桶的顺序合并所有的桶，得到有序数组。
基数排序的关键在于如何确定位数的顺序，如何将数据分配到桶中以及如何对桶中的数据进行合并。通常情况下，基数排序是通过分别处理每个位上的数字来排序的，从最低位到最高位，或者反之。
下面是一个示例，演示基数排序的过程：
原始数组：[170, 45, 75, 90, 802, 24, 2, 66]
- 从最低位（个位）开始，将元素分配到 10 个桶中，根据个位数字的不同。
- 桶 0：170, 90, 802
- 桶 2：2, 802
- 桶 4：24
- 桶 5：75
- 桶 6：66
- 桶 7：
- 桶 8：
- 桶 9：45
- 合并所有的桶，得到有序数组：[170, 90, 802, 2, 24, 75, 66, 45]
Python实现基数排序
下面是Python中的基数排序实现：
def radix_sort(arr):
# 获取数组中的最大值
max_val = max(arr)
# 计算最大值的位数
digit_count = len(str(max_val))
for digit in range(digit_count):
# 创建 10 个桶
buckets = [[] for _ in range(10)]
# 将元素分配到桶中
for num in arr:
digit_val = (num // (10 ** digit)) % 10
buckets[digit_val].append(num)
# 合并所有的桶
arr = []
for bucket in buckets:
arr.extend(bucket)
return arr
- arr 是待排序的整数数组。
- max_val 是数组中的最大值，用于计算位数。
- 计算最大值的位数。
- 创建 10 个桶用于分配数据。
- 将元素分配到对应的桶中，根据位数的不同。
- 合并所有的桶，得到有序数组。
示例代码
下面是一个使用Python进行基数排序的示例代码：
def radix_sort(arr):
max_val = max(arr)
digit_count = len(str(max_val))
for digit in range(digit_count):
buckets = [[] for _ in range(10)]
for num in arr:
digit_val = (num // (10 ** digit)) % 10
buckets[digit_val].append(num)
arr = []
for bucket in buckets:
arr.extend(bucket)
return arr
# 测试排序
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print("排序后的数组:", sorted_arr)
时间复杂度
基数排序的时间复杂度为 O(nk)，其中 n 是数组的长度，k 是最大值的位数。基数排序是一种非比较性排序算法，适用于整数或字符串排序。
总之，基数排序是一种高效的非比较性排序算法，通过分别处理每个位上的数字来排序，从最低位到最高位，或者反之，实现了对整数或字符串数组的排序。了解基数排序有助于理解非比较性排序算法的思想，提供了一种适用于特定场景的排序解决方案。
