第20课：桶排序

学习目标

学完本课后，你将能够：

理解桶排序的核心思想及其与其他排序算法的区别。
掌握桶排序的实现步骤和关键细节。
分析桶排序的时间复杂度和空间复杂度，并了解其最佳适用场景。
能够根据数据特点，选择并实现合适的桶排序方案。

核心概念

桶排序，也称“箱排序”，是一种非常直观的排序算法。它的核心思想是“分而治之”，但与归并排序不同，它的“分”是基于数据的值域。

想象一下，你要整理一堆大小不一的豆子。桶排序的做法是：

准备几个大小相同的桶（比如0-9，10-19，20-29…）。
将每一颗豆子根据其大小放入对应的桶中。
对每个非空的桶内的豆子单独排序（比如用插入排序）。
最后，按照桶的顺序，依次把所有桶里的豆子倒出来，就得到了有序的豆子。

关键点：

均匀分布是前提： 桶排序效率最高的情况是数据能均匀地分散到各个桶中。如果所有数据都挤进同一个桶，它就退化成了对这个桶里的数据单独排序（例如O(n²)的插入排序），失去优势。
映射函数： 如何将数据映射到不同的桶，需要设计一个函数。对于数字，常用 value // bucket_size 或 (value - min) // bucket_size 来计算桶索引。
桶内排序： 每个桶内部需要排序。由于理想情况下每个桶内元素很少，可以使用简单排序（如插入排序）或递归地继续使用桶排序。

时间复杂度分析：

平均/最好情况：O(n + k)
- n 个元素分散到 k 个桶中，假设均匀分布，每个桶有 n/k 个元素。
- 对每个桶排序：k 个桶，每个桶排序时间复杂度为 O((n/k)²)（若用插入排序）。当 n/k 为常数时，这一项为 O(n)。
- 总时间 ≈ O(n)（分发和收集）+ O(n)（排序） = O(n)。
- k 是桶的数量，通常 k 与 n 同数量级或为常数，所以常表示为 O(n)。
最坏情况：O(n²)
- 所有数据都落入同一个桶，此时桶排序退化为对 n 个元素的桶内排序（如插入排序）。

空间复杂度：O(n + k) 需要额外的空间存储 k 个桶，以及将 n 个元素分配到桶中。

代码示例

以下是一个对浮点数列表进行升序排列的桶排序Python实现。我们假设数据范围在 [0, 1)。

def bucket_sort(arr):
    """
    对浮点数列表进行桶排序 (假设数据在 [0, 1) 范围内)
    :param arr: 输入列表
    :return: 排序后的列表
    """
    # 1. 创建桶。桶的数量通常与数据量相关，这里我们简单使用 len(arr) 个桶。
    n = len(arr)
    if n <= 1:
        return arr
    
    # 初始化n个空桶
    buckets = [[] for _ in range(n)]
    
    # 2. 将元素分配到各个桶中
    # 映射函数： value * n 然后取整，得到桶的索引 (0 到 n-1)
    for value in arr:
        # 确保 value 在 [0, 1) 范围内，计算桶索引
        bucket_index = int(value * n)
        # 处理边界情况，例如 value 非常接近 1.0 时，bucket_index 可能等于 n，需要修正
        if bucket_index == n:
            bucket_index = n - 1
        buckets[bucket_index].append(value)
    
    # 3. 对每个非空的桶进行排序（这里使用内置的sorted，实际可以用任何简单排序）
    for i in range(n):
        buckets[i].sort()  # 对桶内元素排序
    
    # 4. 将所有桶中的元素依次合并
    result = []
    for bucket in buckets:
        result.extend(bucket)  # 将桶中已排序的元素添加到结果列表
    
    return result

# 测试代码
if __name__ == "__main__":
    import random
    # 生成10个[0,1)范围内的随机浮点数
    data = [random.random() for _ in range(10)]
    print("原始数据:", [round(x, 4) for x in data])
    
    sorted_data = bucket_sort(data)
    print("排序结果:", [round(x, 4) for x in sorted_data])
    
    # 验证排序是否正确
    print("排序正确?", sorted_data == sorted(data))

输出示例：

原始数据: [0.7825, 0.174, 0.4874, 0.9358, 0.5587, 0.0693, 0.6368, 0.2814, 0.7182, 0.1033]
排序结果: [0.0693, 0.1033, 0.174, 0.2814, 0.4874, 0.5587, 0.6368, 0.7182, 0.7825, 0.9358]
排序正确? True

实践练习

练习1：基础桶排序 给定一个整数列表 arr = [29, 25, 3, 49, 9, 37, 21, 43]，数据范围在 [0, 50)。请实现一个桶排序，将数据分配到5个桶中（桶0: 0-9, 桶1: 10-19, 桶2: 20-29, 桶3: 30-39, 桶4: 40-49）。

要求： 映射函数为 bucket_index = value // 10。每个桶内部使用Python内置的sort()方法排序。
预期输出： [3, 9, 21, 25, 29, 37, 43, 49]

练习2：字符串桶排序 假设我们有一组代表年龄的字符串数字列表：ages = ["5", "3", "12", "9", "35", "18", "7"]。年龄范围在 [0, 100)。

要求： 请使用桶排序对其进行升序排列。你需要先将字符串转换为整数，然后设计合适的桶映射（例如，每10岁一个桶）。注意处理字符串到数字的转换。
预期输出： ["3", "5", "7", "9", "12", "18", "35"] （注意输出为字符串列表）

练习3：优化与分析 假设数据是均匀分布在 [0, 1000) 的浮点数。

要求： 1. 修改上面的基础代码，使其适用于这个范围。2. 尝试改变桶的数量 k（例如，k = 10, k = 100, k = n），并比较在随机生成的 n=10000 个数据上的运行时间（使用 time 模块）。3. 简述你对桶数量选择的观察和理解。

常见错误

忽略数据分布假设： 直接对未知分布的数据使用桶排序，当数据分布极不均匀时，性能可能比 O(n log n) 的算法更差。提示： 在使用前，了解或预估数据分布至关重要。
桶索引计算错误： 映射函数设计不当，导致数据越界（如索引为负数或超出桶数组范围）或所有数据进入同一个桶。提示： 仔细处理边界值，并确保映射结果在 [0, k-1] 范围内。
忘记对桶内元素排序： 这是最常见的低级错误。分发到桶中后，直接合并，结果是无序的。提示： 合并前，必须对每个非空桶进行排序。
空间复杂度理解不足： 桶排序需要额外 O(n+k) 的空间。在内存非常受限的环境下，这可能成为瓶颈。提示： 权衡时间和空间资源。

小结

本节课我们学习了桶排序，一种基于分配思想的高效排序算法。

核心思想： 将数据按值域分配到多个桶中，分别排序后再合并。
时间复杂度： 在数据均匀分布的假设下，平均时间复杂度为优秀的 O(n + k)。最坏情况（数据集中于一个桶）退化为桶内排序的时间复杂度（如 O(n²)）。
适用场景： 特别适合数据均匀分布在某个已知范围内的场景，例如浮点数排序、已知范围的整数排序。
关键步骤： 1. 创建桶；2. 按映射规则分配数据；3. 桶内排序；4. 合并结果。
重要提醒： 桶排序的性能高度依赖于数据的分布和桶的数量选择。在实际应用中，需要根据数据特征来决定是否采用以及如何配置桶。

理解桶排序有助于你掌握“空间换时间”和“分治”的算法设计思想，并为后续学习哈希表等数据结构打下基础。下一节课，我们将开始学习非排序类的基础算法——线性搜索。

练习编辑器

rust