Python 排序算法：桶排序（Bucket Sort）

# /*
# Python 排序算法：桶排序（Bucket Sort）
# --------------------------------------------------------
# 概念：
# 桶排序是一种基于“分桶思想”的线性时间排序方法，
# 将数据分布到多个桶中，再分别排序，最后合并。
#
# 特点：
# 1) 平均时间复杂度 O(n)
# 2) 稳定排序
# 3) 需要额外空间
# */

# --------------------------------------------------------
# 桶排序算法实现（已修复 bucket_count 类型问题）
def bucket_sort(arr, bucket_size=5):
    if len(arr) < 2:
        return arr

    # 最大、最小值
    min_val = min(arr)
    max_val = max(arr)

    # 修复：确保桶数量为整数
    bucket_count = int((max_val - min_val) / bucket_size) + 1

    # 创建空桶
    buckets = [[] for _ in range(bucket_count)]

    # --------------------------------------------------------
    # 将数据放入桶中
    for num in arr:
        index = int((num - min_val) / bucket_size)
        buckets[index].append(num)

    # --------------------------------------------------------
    # 对每个桶排序并合并
    sorted_arr = []
    for bucket in buckets:
        if bucket:
            bucket.sort()
            sorted_arr.extend(bucket)

    return sorted_arr

# --------------------------------------------------------
# 示例演示
data = [0.42, 4.2, 3.5, 2.3, 0.12, 5.0, 3.14, 2.78]

print("原始数据：", data)

sorted_data = bucket_sort(data, bucket_size=1)

print("桶排序结果：", sorted_data)

# --------------------------------------------------------
# 要点总结：
# 1) 桶排序依赖数据分布均匀；
# 2) 桶内部可使用任意排序方法；
# 3) 对浮点数排序效果更佳；
# 4) bucket_count 需要为整型。
# */

# 原始数据： [0.42, 4.2, 3.5, 2.3, 0.12, 5.0, 3.14, 2.78]
# 桶排序结果： [0.12, 0.42, 2.3, 2.78, 3.14, 3.5, 4.2, 5.0]