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]
1

首先，我们创建 10 个桶，每个桶代表一个数字范围，例如，第一个桶包含 0 到 9 之间的数字，第二个桶包含 10 到 19 之间的数字，以此类推。

Bucket 0: [ ]
Bucket 1: [ ]
Bucket 2: [ ]
...
Bucket 9: [ ]
1
2
3
4
5

然后，我们将列表中的元素分别放入这些桶中，根据个位数的值将它们分配到不同的桶中。

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]
1
2
3
4
5
6
7
8
9
10

接下来，我们对每个桶中的元素进行排序，这里我们可以使用任何排序算法，如插入排序。

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]
1
2
3
4
5
6
7
8
9
10

最后，我们按顺序合并这些桶，得到排序后的结果。

[12, 17, 21, 23, 26, 39, 68, 72, 78, 94]
1

这就是桶排序的基本过程。请注意，桶排序对于小范围内的整数或浮点数非常高效，但对于稀疏数据或数据范围较大的情况，可能不如其他排序算法高效。

什么是基数排序？

基数排序是一种非比较性排序算法，它将整数按照位数进行排序。基数排序通常用于对整数进行排序，特别是对于具有相同位数的整数集合。

基数排序的基本步骤

• 1 . 将整数按照个位数的值分成 10 个桶，每个桶包含相同个位数的整数。
• 2 . 将这些桶按顺序合并，得到一个部分排序的序列。
• 3 . 重复以上两个步骤，但这次按照十位数进行排序。
• 4 . 继续重复，直到按照最高位进行排序。

基数排序的示例

让我们看一个基数排序的示例，假设我们有一个整数列表：

[170, 45, 75, 90, 802, 24, 2, 66]
1

首先，我们按照个位数的值将它们分成 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: []
1
2
3
4
5
6
7
8
9
10

然后，我们按照桶的顺序合并它们，得到一个部分排序的序列：

[170, 90, 802, 2, 24, 45, 75, 66]
1

接下来，我们按照十位数的值将它们再次分成 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]
1
2
3
4
5
6
7
8
9
10

再次按照桶的顺序合并它们：

[802, 2, 24, 45, 75, 66, 170, 90]
1

最后，我们按照百位数的值将它们分成 10 个桶，然后合并它们：

[2, 24, 45, 66, 75, 90, 170, 802]
1

这就是基数排序的基本过程。它对于整数排序非常高效，尤其是当整数具有相同位数时。但对于不同位数的整数，需要在每一轮排序后重新分桶，因此它不太适合对范围广泛的整数排序。

桶排序与基数排序的应用

桶排序的应用

桶排序最适合用于排序 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

总结

桶排序和基数排序是两种非常有趣的排序算法，它们对于特定类型的数据和应用非常高效。桶排序适合于均匀分布的小数排序，而基数排序适合于整数排序，特别是具有相同位数的整数。通过将这些算法加入你的工具箱，你可以更好地处理各种排序问题，提高性能并应对不同类型的数据。希望这篇文章对你理解桶排序和基数排序有所帮助。

[ 专栏推荐 ]
😃 《Python 算法初阶：入门篇》😄
❤️【简介】：本课程是针对 Python 初学者设计的算法基础入门课程，涵盖算法概念、时间复杂度、空间复杂度等基础知识。通过实例演示线性搜索、二分搜索等算法，并介绍哈希表、深度优先搜索、广度优先搜索等搜索算法。此课程将为学员提供扎实的 Python 编程基础与算法入门，为解决实际问题打下坚实基础。