桶子排序是什么？

桶子排序是一种 把资料分类再逐一排序 的演算法。想像一下你有一堆数字，目标是从小到大排列，但这堆数字范围很大、分布也不均匀。

因此桶子排序的想法就是：
(1) 先根据数字的范围，把它们分进不同的「桶子」里。
(2) 每个桶子里的数字再个别进行排序。
(3) 最后把所有桶子的内容合併在一起，这样数字就排好了！

通常在撰写过程，可注意以下细节

  • 检查特殊情况： 如果输入的数字列是空的，或所有数字都一样，那直接回传原本的就好，不需要排序。
  • 计算范围： 找出数字的 最小值 和 最大值，用来决定每个桶子的范围大小（例如，范围是 0~100，就可以分成 10 个桶子，每个桶子范围是 10）。
  • 分桶： 根据每个数值，算出应该放到哪个桶子（例如 25 放进第 2 个桶，89 放进第 8 个桶）。
  • 桶内排序： 每个桶子内的数字，使用 Python 内建的排序功能（这样速度快又稳定）。
  • 合併结果： 把所有桶子的内容依序取出来，合併成最后的排序结果。

    • 示意图

    实作

    def bucket_sort(arr, num_buckets=10):
    """
    通用桶子排序算法，适用于小数与整数
    para:
    arr: 输入数字列表
    num_buckets: 桶的数量 (预设 10)
    return:
    排序后的列表
    """
    if not arr:
    return arr # 空阵列直接回传

    # 计算数值范围
    min_val, max_val = min(arr), max(arr)
    if min_val == max_val:
    return arr # 全部数值相同直接回传

    # 建立桶阵列
    buckets = [[] for _ in range(num_buckets)]
    bucket_range = (max_val - min_val) / num_buckets

    # 把数字分配到对应的桶
    for num in arr:
    idx = int((num - min_val) / bucket_range)
    idx = min(idx, num_buckets - 1) # 确保最大值进入最后一个桶
    buckets[idx].append(num)

    # 各桶子排序并合併结果
    return [num for bucket in buckets for num in sorted(bucket)]

    # 测试五种情境
    if __name__ == "__main__":
    test_cases = [
    [13.5, 0.2, 7.8, 10.1, 1.23, 5.5, 3.14, 8.9], # 小数
    [100, 2, 56, 32, 89, 12, 45], # 整数
    [0.001, 1000.5, 25.7, 500.2, 0.12, 89.2], # 范围很大
    [1, 1, 1, 1, 1], # 相同数值
    [5], # 单一值
    [] # 空值
    ]
    print("桶子排序测试\\n" + "="*100)
    for i, case in enumerate(test_cases, 1):
    print(f"测试案例 {i}: \\n原始数组 : {case}")
    print(f"排序结果 : {bucket_sort(case)}\\n")

    程式码产出如下:

    桶子排序测试
    ====================================================================================================
    测试案例 1:
    原始数组 : [13.5, 0.2, 7.8, 10.1, 1.23, 5.5, 3.14, 8.9]
    排序结果 : [0.2, 1.23, 3.14, 5.5, 7.8, 8.9, 10.1, 13.5]

    测试案例 2:
    原始数组 : [100, 2, 56, 32, 89, 12, 45]
    排序结果 : [2, 12, 32, 45, 56, 89, 100]

    测试案例 3:
    原始数组 : [0.001, 1000.5, 25.7, 500.2, 0.12, 89.2]
    排序结果 : [0.001, 0.12, 25.7, 89.2, 500.2, 1000.5]

    测试案例 4:
    原始数组 : [1, 1, 1, 1, 1]
    排序结果 : [1, 1, 1, 1, 1]

    测试案例 5:
    原始数组 : [5]
    排序结果 : [5]

    测试案例 6:
    原始数组 : []
    排序结果 : []

    备注 (for 眼尖的人)

    各位应该到这边，应该会有一个疑问，既然我在程式码中就用了 sort 这个指令，为什么我还需要桶子排序? 直接sort一下就行了阿?最大的原因在于，桶子排序先分类再排序，可以减少 sort 的计算时间 (直觉: 给你一堆数值要你去排序，跟帮你分类好再请你排序，谁会比较好排? 显然是后者会更有效率)

    因此桶子排序的核心概念是 分类加速，将资料划分为多个小范围（桶），仅对桶内资料排序后合併，完成排序。且其优势在于时间复杂度接近 O(n) (最差就顶多与sort 的 O(n log n) 一样) ，当资料符合以下条件时会感受到极大效率的差异：

    (1) 资料分布均匀：均匀分布的资料使每个桶内的资料量接近平均，可大幅减少排序成本，接近线性排序。(2) 资料范围大且分布明确：范围大的资料，若使用桶子排序可以按范围划分，可以缩小排序范围，比直接用 sort() 更高效。

    所以，如果资料分布均匀且范围大，桶子排序能够帮助你更好的提高资料处里效率，特别适合巨量资料处理。而对于范围小或随机分布的资料，直接用 sort() 会更简单且快速~