def bucket_sort(arr, bucket_size=5):
    """
    桶排序算法實現(xiàn)
    參數(shù):
    arr: 待排序的數(shù)組
    bucket_size: 每個桶的大小范圍，默認(rèn)值為5
    返回:
    排序后的數(shù)組
    """
    if len(arr) == 0:
        return arr
    # 步驟1：確定數(shù)據(jù)的最大值和最小值
    min_value = min(arr)
    max_value = max(arr)
    # 步驟2：計算需要的桶數(shù)量
    bucket_count = (max_value - min_value) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    # 步驟3：將數(shù)據(jù)分配到各個桶中
    for i in range(len(arr)):
        # 計算當(dāng)前元素應(yīng)該放入哪個桶
        index = (arr[i] - min_value) // bucket_size
        buckets[index].append(arr[i])
    # 步驟4：對每個桶進(jìn)行排序（這里使用內(nèi)置排序，也可用其他排序算法）
    for i in range(bucket_count):
        buckets[i].sort()
    # 步驟5：將排序后的桶按順序合并
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)
    return sorted_arr
# 測試示例
if __name__ == "__main__":
    # 測試數(shù)據(jù)1：均勻分布的整數(shù)
    test_data1 = [29, 25, 3, 49, 9, 37, 21, 43]
    print("原始數(shù)據(jù):", test_data1)
    sorted_data1 = bucket_sort(test_data1)
    print("桶排序結(jié)果:", sorted_data1)
    # 測試數(shù)據(jù)2：包含小數(shù)的數(shù)據(jù)
    test_data2 = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
    print("
原始數(shù)據(jù):", test_data2)
    sorted_data2 = bucket_sort(test_data2, bucket_size=0.1)
    print("桶排序結(jié)果:", sorted_data2)

def grade_sort(grades):
    """學(xué)生成績桶排序示例"""
    buckets = [[] for _ in range(11)]  # 11個桶對應(yīng)0-100分
    for grade in grades:
        bucket_index = grade // 10
        buckets[bucket_index].append(grade)
    # 對每個桶排序
    for bucket in buckets:
        bucket.sort()
    # 合并結(jié)果
    return [grade for bucket in buckets for grade in bucket]
# 測試成績排序
grades = [85, 92, 78, 65, 95, 88, 72, 60, 98, 83]
sorted_grades = grade_sort(grades)
print(f"原始成績: {grades}")
print(f"排序后成績: {sorted_grades}")

def float_bucket_sort(floats):
    """浮點數(shù)桶排序"""
    min_val = min(floats)
    max_val = max(floats)
    
    # 創(chuàng)建10個桶
    bucket_count = 10
    buckets = [[] for _ in range(bucket_count)]
    
    # 分配數(shù)據(jù)到桶中
    for num in floats:
        index = int((num - min_val) / (max_val - min_val) * (bucket_count - 1))
        buckets[index].append(num)
    
    # 桶內(nèi)排序并合并
    result = []
    for bucket in buckets:
        bucket.sort()
        result.extend(bucket)
    
    return result

def adaptive_bucket_sort(arr):
    """自適應(yīng)桶大小的桶排序"""
    if not arr:
        return arr
    
    min_val, max_val = min(arr), max(arr)
    range_val = max_val - min_val
    
    # 根據(jù)數(shù)據(jù)范圍自適應(yīng)確定桶數(shù)量
    if range_val < 100:
        bucket_size = 10
    elif range_val < 1000:
        bucket_size = 100
    else:
        bucket_size = range_val // 100
    
    return bucket_sort(arr, bucket_size)

def recursive_bucket_sort(arr, bucket_size=5, depth=0, max_depth=3):
    """遞歸桶排序，防止桶內(nèi)數(shù)據(jù)過多"""
    if len(arr) <= 1 or depth > max_depth:
        return sorted(arr)
    
    min_val, max_val = min(arr), max(arr)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    
    for num in arr:
        index = (num - min_val) // bucket_size
        buckets[index].append(num)
    
    result = []
    for bucket in buckets:
        if len(bucket) > 10:  # 如果桶內(nèi)元素過多，遞歸排序
            sorted_bucket = recursive_bucket_sort(bucket, bucket_size, depth + 1, max_depth)
        else:
            sorted_bucket = sorted(bucket)
        result.extend(sorted_bucket)
    
    return result