桶排序算法 Python

def bucket_sort(arr, bucket_size=5):
    """
    桶排序算法（升序）
    :param arr: 待排序列表（元素应为非负数值，可扩展处理负数）
    :param bucket_size: 每个桶的容量范围（控制桶的数量）
    :return: 新列表（非原地排序）
    """
    if not arr:
        return []

    # 1. 确定最小值和最大值，以便映射桶索引
    min_val = min(arr)
    max_val = max(arr)

    # 如果所有值相等，直接返回
    if min_val == max_val:
        return arr[:]

    # 2. 计算桶的数量
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    # 3. 将元素分配到各个桶中
    for num in arr:
        # 计算桶索引（基于最小值的偏移量）
        idx = (num - min_val) // bucket_size
        buckets[idx].append(num)

    # 4. 对每个桶内部排序（这里使用内置排序，也可用插入排序等）
    sorted_arr = []
    for bucket in buckets:
        bucket.sort()          # 桶内排序
        sorted_arr.extend(bucket)   # 合并结果

    return sorted_arr


# 扩展版本：支持负数和浮点数（使用相同逻辑）
def bucket_sort_advanced(arr, bucket_size=5):
    """支持负数、浮点数的桶排序"""
    if not arr:
        return []
    min_val, max_val = min(arr), max(arr)
    if min_val == max_val:
        return arr[:]

    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        idx = int((num - min_val) // bucket_size)  # 浮点需转为int
        buckets[idx].append(num)

    sorted_arr = []
    for bucket in buckets:
        bucket.sort()
        sorted_arr.extend(bucket)
    return sorted_arr


# 测试示例
if __name__ == "__main__":
    # 基本测试（整数）
    test_array = [29, 25, 3, 49, 9, 37, 21, 43]
    print("原始数组:", test_array)
    sorted_array = bucket_sort(test_array, bucket_size=10)
    print("桶排序后:", sorted_array)

    # 边界测试
    print("\n边界测试:")
    print("空数组:", bucket_sort([]))
    print("单元素数组:", bucket_sort([42]))
    print("已排序数组:", bucket_sort([1, 2, 3, 4, 5]))
    print("逆序数组:", bucket_sort([5, 4, 3, 2, 1]))
    print("含重复元素:", bucket_sort([3, 1, 4, 1, 5, 9, 2, 6]))
    print("均匀分布整数:", bucket_sort([10, 20, 30, 40, 50, 60, 70, 80, 90]))

    # 浮点数测试
    float_arr = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
    print("\n浮点数数组:", float_arr)
    print("浮点数排序:", bucket_sort_advanced(float_arr, bucket_size=0.1))

    # 负数测试
    negative_arr = [-5, -2, -10, -1, -8, -3]
    print("负数数组:", negative_arr)
    print("负数排序:", bucket_sort_advanced(negative_arr, bucket_size=2))