数据结构与算法 / 系统课时

桶排序

桶排序

桶排序先把数据映射到多个范围较小的桶中,再分别排序并按桶顺序合并。本课以区间 [0, 1) 内的浮点数为例,完整实现分桶、桶内排序和结果合并,并解释为什么数据分布会直接影响性能。

学习目标

  • 理解桶排序的分桶、桶内排序和合并过程。
  • 能够为已知取值范围设计正确的桶索引公式。
  • 能够分析均匀分布假设成立与失效时的复杂度差异。

核心原理与执行流程

桶排序利用数据取值范围已知的条件,将整个值域划分为若干按数值递增排列的区间。算法先把每个元素放入对应桶,再独立排序每个桶,最后按桶编号从小到大拼接。由于前一个桶中的所有值都不大于后一个桶中的值,合并时不需要再次进行跨桶比较。

对长度为 nn、取值位于 [0, 1) 的数组,可以创建 nn 个桶,并使用 index = int(value * n) 计算桶编号。在数学上,桶编号范围为 0 到 n - 1,第 i 个桶对应区间 [i/n, (i+1)/n)。浮点运算可能改变极接近分界线的归桶结果。示例先验证原值,再把桶号限制在合法范围。映射对合法输入保持非递减,因此只要各桶内部排序,拼接仍然有序。

桶排序分桶与合并过程

例如数组长度为 10 时,0.12 和 0.17 都进入编号为 1 的桶,0.21、0.23 和 0.26 进入编号为 2 的桶。先将各桶内部排好序,再依次读取桶 0 到桶 9,就能得到完整的升序序列。空桶直接跳过,不影响排序结果。

桶数量不是越多越好。桶太少会让单个桶承担大量排序工作;桶太多则增加容器创建和遍历开销。桶内可以使用插入排序、归并排序或语言内置排序,选择取决于桶大小、性能和稳定性要求。本课使用 Python 的 list.sort(),它具有稳定排序特性。

复杂度与分布假设

设元素数量为 nn,桶数量为 kk。分配元素需要 O(n)O(n) 时间,创建和遍历桶需要 O(k)O(k) 时间,因此不考虑桶内排序时,分桶与合并的总成本为 O(n+k)O(n+k)。真正的运行时间还取决于各桶内部的元素数量和所采用的排序算法。

设 NiN_i 是桶 i 的元素数。∑iNi2\sum_i N_i^2 等于 n 加上落入同一桶的不同元素有序对数。若 n 个元素独立且每个等概率落入 k 个桶,每对同桶的概率是 1/k1/k,所以 E[∑iNi2]=n+n(n−1)/k\mathbb E[\sum_i N_i^2]=n+n(n-1)/k。当 k 与 n 同阶时,即使桶内排序以平方时间作上界,总期望时间也为线性。若所有元素都复制自同一次均匀抽样,单个元素仍均匀,但它们始终同桶,独立假设失效。

最坏情况下,所有元素可能进入同一个桶,整体性能就由桶内排序决定。例如使用本课的 list.sort(),最坏时间复杂度为 O(nlog⁡n)O(n \log n);如果使用普通插入排序,则可能退化为 O(n2)O(n^2)。额外空间主要用于桶及其存放的元素,通常为 O(n+k)O(n+k),当 k=nk=n 时为 O(n)O(n)。

正确性还依赖取值范围。本课的分桶公式仅适用于 [0, 1),其中 1.0 不属于合法输入,不能直接计算桶编号。对于一般闭区间 [minimum, maximum],可使用 min(k - 1, int((value - minimum) / (maximum - minimum) * k)) 计算桶编号;上下界相等时单独处理,浮点端点相差极大时还要防止减法溢出为无穷,必要时先用可验证的缩放方式归一化。即使公式正确,数据明显偏斜时也可能产生较大的桶。

完整可运行示例

将下面代码保存为 bucket_sort_demo.py。示例使用与数组长度相同的桶数量,调用 Python 的 list.sort() 完成桶内排序,并将结果写回原数组。函数接收可变列表。排序前验证元素是内置 int 或 float 且位于 [0, 1),范围判断也排除 NaN 和无穷大。

python
def bucket_sort(values):
    if not isinstance(values, list):
        raise TypeError("values must be a list")
    if not values:
        return values

    # 修改原数组之前先验证范围,拒绝 NaN、无穷大和 1.0。
    if any(type(value) not in (int, float) or not 0.0 <= value < 1.0
           for value in values):
        raise ValueError("all values must be finite numbers in [0, 1)")

    bucket_count = len(values)
    buckets = [[] for _ in range(bucket_count)]

    # 对浮点乘法的舍入误差做上界保护,避免索引越界。
    for value in values:
        index = min(int(value * bucket_count), bucket_count - 1)
        buckets[index].append(value)

    # 各桶内部排序后,按桶编号依次写回原数组。
    write_index = 0
    for bucket in buckets:
        bucket.sort()
        for value in bucket:
            values[write_index] = value
            write_index += 1

    return values


def main():
    numbers = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
    print("排序前:", numbers)
    bucket_sort(numbers)
    print("排序后:", numbers)


if __name__ == "__main__":
    main()

在保存文件的目录中运行以下命令,使用 Python 3 执行程序。

bash
python bucket_sort_demo.py

预期输出

text
排序前: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
排序后: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

核对该样例时,除了检查非递减顺序,还可与 sorted 的结果逐项对照,确认未丢失或重复元素。函数会直接修改传入的列表,同时返回同一个列表;对于空列表则原样返回。将输入元素改为 1.0 或 float('nan') 时,程序会抛出 ValueError,而不是继续执行无效的分桶操作。

如果实际数据大量集中在少数几个桶中,应先检查桶索引公式是否覆盖完整取值范围,再观察各桶的元素数量。对于明显偏斜的数据,可以调整桶边界、采用非等宽桶,或者直接使用 list.sort() 等通用比较排序。桶排序适合取值范围明确、数据分布可预估的场景;当分布未知且难以控制时,不应仅凭平均线性复杂度就认定它一定更快。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

桶排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通