专题进阶 · 排序算法推荐总顺序 · 第 32 / 148 课

区分分桶与计数,推导分布假设如何影响桶内成本。

先学会这些,再进入本课 插入排序 计数排序
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 排序算法

桶排序Bucket Sort

按数值范围分桶,再分别排序;均匀分布假设影响平均效率。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

区分分桶与计数,推导分布假设如何影响桶内成本。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

一批落在 [0,1) 的小数,需要排序。值不是小整数,不能直接开频次表,该怎么做?

02一步步得到方法

把连续区间切成有序的桶

设 k 个桶,用 floor(kx) 将 x 放入第 0..k−1 个桶。桶之间有自然大小关系:较早桶的所有值不大于较晚桶的值,但同桶中的小数仍需排序。

计数排序的一个桶代表一个确切整数,桶排序的一个桶代表一段范围,所以不能只计数后重建值。本课在每个桶内做插入排序,再按桶编号拼接。

平均线性依赖均匀性

若 k 约为 n 且独立均匀分布,每个桶平均只有常数个元素,桶内排序总成本通常线性。更准确地看,是各桶大小平方之和 Σbᵢ²,而不是只看平均桶大小。

若所有值都集中到一个桶,插入排序会退化到 O(n²)。分桶函数与数据分布不匹配时,多开桶也可能无助;应测量桶占用或使用更强的桶内排序。

桶间顺序和桶内顺序分别保证

映射到桶的规则应保持值的大小关系:前一个桶的所有值不大于后一个桶。这样每个桶内部排好,再按桶次序拼接才得到整体有序。

平均接近线性的收益依赖分布与桶数量。如果绝大多数元素落在同一个桶,成本会接近该桶所用排序的最坏情况。选择映射之前应看数据范围和分布,而不是只看输入长度。

03把一个小例子完全算清楚

[0.42,0.11,0.35,0.09],k=4。

步骤计算与状态为什么这样做
映射桶号分别 1、0、1、0floor(4x)
桶 0[0.11,0.09] → [0.09,0.11]桶内插入排序
桶 1[0.42,0.35] → [0.35,0.42]两个空桶无需处理
拼接[0.09,0.11,0.35,0.42]桶序加桶内序

窄屏可左右滑动表格,阅读完整计算与理由。

分桶只解决跨区间顺序,桶内排序解决剩余不确定性。

04为什么这个方法成立

  1. 桶映射随数值单调,前一桶任一值不会大于后一桶任一值。
  2. 每个桶独立排序后局部有序。
  3. 按桶序连接这些局部序列,得到全局有序序列。

05把推导翻译成代码

Python · 可独立运行的教学实现

def bucket_sort(a):
    if any(not 0 <= x < 1 for x in a):
        raise ValueError("requires 0 <= x < 1")
    k = max(1, len(a))
    buckets = [[] for _ in range(k)]
    for x in a:
        buckets[int(k*x)].append(x)
    for b in buckets:
        for i in range(1, len(b)):
            key, j = b[i], i
            while j and b[j-1] > key:
                b[j] = b[j-1]
                j -= 1
            b[j] = key
    return [x for b in buckets for x in b]

逐个理解关键决定

0 <= x < 1
右端点不包含 1,否则会产生越界桶号 k;换范围必须重新定义映射。
[[] for _ in range(k)]
每个桶独立,不能用 [[]]*k 共享同一列表。

06时间、空间与实现范围

时间 O(n+k+Σbᵢ²),最坏 O(n²),均匀假设和 k≈n 下期望 O(n)。

桶、元素引用和输出总空间 O(n+k)。稳定性还依赖桶内排序与拼接实现。

07改变条件,检查哪里会出错

把均匀分布当成所有数据的性质

集中分布会产生大桶,应记录分布假设并给最坏情况。

输入范围变化却沿用 floor(kx)

先规范化到明确区间,单独处理最大值落在右边界的情况。

最大值恰好落到桶数位置

浮点归一化映射要处理右端点,避免产生等于桶数量的越界下标。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

输入全部为 0.99 时会怎样?

需要一点提示

桶号相同。

查看解析与答案

都落最后一桶;本例相同值不移动,但换成同桶内逆序小数会触发平方级桶内工作。

练习 2 · 边界与辨析

为什么平均桶大小为 1 仍不保证每个桶都小?

需要一点提示

平均值不能限制最大值。

查看解析与答案

可以一个桶装 n 个,其余为空;决定工作量的是平方和和分布。

练习 3 · 变式与迁移

将桶内排序换成归并有何影响?

需要一点提示

求和 bᵢlog bᵢ。

查看解析与答案

最坏桶内总时间 O(n log n),但平均常数与额外空间可能变化。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 排序

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。