Python 算法高级篇：桶排序与基数排序
Python 算法高级篇：桶排序与基数排序
引言
在算法高级篇的课程中，我们将探讨两种非常有趣的排序算法：桶排序（ Bucket Sort ）和基数排序（ Radix Sort ）。这两种排序算法虽然不如快速排序和归并排序那样出名，但在某些特定情况下，它们能够以线性时间复杂度（ O ( n )）运行，而不是标准排序算法的 O ( n log n )。
什么是桶排序？
桶排序是一种分布式排序算法，它将元素分为若干个"桶"，然后分别对每个桶进行排序。最后，将这些桶按顺序合并以获得排好序的结果。这个算法的性能非常依赖于数据的分布，对于均匀分布的数据，它的性能会非常好。
桶排序的基本步骤
- 1 . 创建一定数量的空桶，这些桶的数量可以根据输入数据的范围来确定。
- 2 . 将每个元素放入对应的桶中。元素的放入可以使用不同的策略，最简单的是线性映射，即将数据范围均匀分配到各个桶中。
- 3 . 对每个非空的桶进行排序，可以使用其他排序算法，或者递归使用桶排序。
- 4 . 将各个桶中的元素按顺序合并，得到排序后的结果。
桶排序的示例
让我们看一个简单的桶排序示例，假设我们有一个包含 0 到 99 之间整数的列表：
[78, 17, 39, 26, 72, 94, 21, 12, 23, 68]首先，我们创建 10 个桶，每个桶代表一个数字范围，例如，第一个桶包含 0 到 9 之间的数字，第二个桶包含 10 到 19 之间的数字，以此类推。
Bucket 0: [ ]
Bucket 1: [ ]
Bucket 2: [ ]
...
Bucket 9: [ ]然后，我们将列表中的元素分别放入这些桶中，根据个位数的值将它们分配到不同的桶中。
Bucket 0: [78]
Bucket 1: [21]
Bucket 2: [12, 72, 23]
Bucket 3: [39]
Bucket 4: []
Bucket 5: [26]
Bucket 6: []
Bucket 7: [17]
Bucket 8: [68]
Bucket 9: [94]接下来，我们对每个桶中的元素进行排序，这里我们可以使用任何排序算法，如插入排序。
Bucket 0: [78]
Bucket 1: [21]
Bucket 2: [12, 23, 72]
Bucket 3: [39]
Bucket 4: []
Bucket 5: [26]
Bucket 6: []
Bucket 7: [17]
Bucket 8: [68]
Bucket 9: [94]最后，我们按顺序合并这些桶，得到排序后的结果。
[12, 17, 21, 23, 26, 39, 68, 72, 78, 94]这就是桶排序的基本过程。请注意，桶排序对于小范围内的整数或浮点数非常高效，但对于稀疏数据或数据范围较大的情况，可能不如其他排序算法高效。
什么是基数排序？
基数排序是一种非比较性排序算法，它将整数按照位数进行排序。基数排序通常用于对整数进行排序，特别是对于具有相同位数的整数集合。
基数排序的基本步骤
- 1 . 将整数按照个位数的值分成 10 个桶，每个桶包含相同个位数的整数。
- 2 . 将这些桶按顺序合并，得到一个部分排序的序列。
- 3 . 重复以上两个步骤，但这次按照十位数进行排序。
- 4 . 继续重复，直到按照最高位进行排序。
基数排序的示例
让我们看一个基数排序的示例，假设我们有一个整数列表：
[170, 45, 75, 90, 802, 24, 2, 66]首先，我们按照个位数的值将它们分成 10 个桶：
Bucket 0: [170, 90]
Bucket 1: []
Bucket 2: [802, 2]
Bucket 3: []
Bucket 4: [24]
Bucket 5: [45, 75]
Bucket 6: [66]
Bucket 7: []
Bucket 8: []
Bucket 9: []然后，我们按照桶的顺序合并它们，得到一个部分排序的序列：
[170, 90, 802, 2, 24, 45, 75, 66]接下来，我们按照十位数的值将它们再次分成 10 个桶：
Bucket 0: [802, 2]
Bucket 1: []
Bucket 2: []
Bucket 3: [24]
Bucket 4: [45]
Bucket 5: [75]
Bucket 6: [66]
Bucket 7: []
Bucket 8: []
Bucket 9: [170, 90]再次按照桶的顺序合并它们：
[802, 2, 24, 45, 75, 66, 170, 90]最后，我们按照百位数的值将它们分成 10 个桶，然后合并它们：
[2, 24, 45, 66, 75, 90, 170, 802]这就是基数排序的基本过程。它对于整数排序非常高效，尤其是当整数具有相同位数时。但对于不同位数的整数，需要在每一轮排序后重新分桶，因此它不太适合对范围广泛的整数排序。
桶排序与基数排序的应用
桶排序的应用
桶排序最适合用于排序 0 到 1 之间的小数，比如在计算机图形学中对颜色的排序，或者对学生成绩的百分比排序。在这些情况下，数据是均匀分布的，桶排序可以在线性时间内完成排序。
基数排序的应用
基数排序通常用于排序整数，特别是具有相同位数的整数。它在处理大整数的计算中也非常有用，例如大整数的加法和乘法运算。
Python 示例代码
下面是 Python 中的桶排序和基数排序的示例代码：
# 桶排序
def bucket_sort(arr):
# 创建空桶
buckets = [[] for _ in range(10)]
# 将元素分配到桶中
for num in arr:
index = num // 10
buckets[index].append(num)
# 对每个桶中的元素进行排序
for i in range(10):
buckets[i] = sorted(buckets[i])
# 合并桶
result = []
for bucket in buckets:
result.extend(bucket)
return result
# 基数排序
def radix_sort(arr):
# 计算最大位数
max_num = max(arr)
digits = len(str(max_num))
for i in range(digits):
# 创建空桶
buckets = [[] for _ in range(10)]
# 将元素分配到桶中
for num in arr:
index = (num // 10**i) % 10
buckets[index].append(num)
# 合并桶
arr = []
for bucket in buckets:
arr.extend(bucket)
return arr
# 测试桶排序
arr1 = [78, 17, 39, 26, 72, 94, 21, 12, 23, 68]
sorted_arr1 = bucket_sort(arr1)
print("桶排序结果:", sorted_arr1)
# 测试基数排序
arr2 = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr2 = radix_sort(arr2)
print("基数排序结果:", sorted_arr2)总结
桶排序和基数排序是两种非常有趣的排序算法，它们对于特定类型的数据和应用非常高效。桶排序适合于均匀分布的小数排序，而基数排序适合于整数排序，特别是具有相同位数的整数。通过将这些算法加入你的工具箱，你可以更好地处理各种排序问题，提高性能并应对不同类型的数据。希望这篇文章对你理解桶排序和基数排序有所帮助。