Python桶排序详解（从零开始掌握高效的桶排序算法）

桶排序的基本步骤

1. 创建若干个空桶（通常用列表表示）；
2. 遍历原始数组，将每个元素放入对应的桶中（根据数值范围分配）；
3. 对每个非空桶内的元素进行排序（常用插入排序或快速排序）；
4. 按顺序将所有桶中的元素合并回原数组。

Python桶排序实现

下面是一个完整的Python桶排序实现示例。我们假设输入的数据是 [0, 1) 区间内的浮点数（这是桶排序最典型的应用场景）：

def bucket_sort(arr):    if len(arr) == 0:        return arr        # 1. 创建空桶    bucket_count = len(arr)    buckets = [[] for _ in range(bucket_count)]        # 2. 将元素分配到桶中    for num in arr:        # 假设所有数都在 [0, 1) 范围内        index = int(num * bucket_count)        # 防止 index 超出范围（例如 num=1.0 时）        if index >= bucket_count:            index = bucket_count - 1        buckets[index].append(num)        # 3. 对每个桶进行排序    for bucket in buckets:        bucket.sort()  # 使用 Python 内置排序（Timsort）        # 4. 合并所有桶    result = []    for bucket in buckets:        result.extend(bucket)        return result# 测试示例if __name__ == "__main__":    data = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]    sorted_data = bucket_sort(data)    print("原始数据:", data)    print("排序后:", sorted_data)

处理整数数组的桶排序

如果你要排序的是整数数组，只需稍作修改。关键在于如何将整数映射到桶中。以下是一个通用版本：

def bucket_sort_int(arr):    if not arr:        return arr        min_val, max_val = min(arr), max(arr)    bucket_range = (max_val - min_val) / len(arr)    buckets = [[] for _ in range(len(arr))]        for num in arr:        if bucket_range == 0:  # 所有元素相同            index = 0        else:            index = int((num - min_val) // bucket_range)            if index >= len(arr):                index = len(arr) - 1        buckets[index].append(num)        # 对每个桶排序    for bucket in buckets:        bucket.sort()        # 合并结果    result = []    for bucket in buckets:        result.extend(bucket)        return result# 测试整数排序nums = [29, 25, 3, 49, 9, 37, 21, 43]print("整数排序前:", nums)print("整数排序后:", bucket_sort_int(nums))

桶排序的优缺点

优点：

• 在数据分布均匀时，时间复杂度接近线性 O(n)；
• 稳定排序（如果桶内排序是稳定的）；
• 适合处理大规模浮点数数据。

缺点：

• 需要额外的存储空间（O(n + k)）；
• 当数据分布不均匀时，性能会退化；
• 不适合处理离散范围很大的整数。

总结

通过本教程，你已经掌握了Python桶排序的基本原理和实现方法。无论是处理浮点数还是整数，只要理解了桶的分配逻辑，就能灵活应用这一高效的桶排序算法。

建议你在实际项目中根据数据特点选择合适的排序算法。对于初学者来说，多动手编写和调试代码是掌握Python排序教程内容的最佳方式。

希望这篇关于桶排序实现的详细指南对你有所帮助！