桶排序（Bucket Sort） - 数据结构与算法-上海佼艾

一、算法概述

桶排序（Bucket Sort），也称箱排序，是一种基于分治思想的排序算法。它将元素分散到若干个有序的"桶"中，每个桶内的元素再分别进行排序，最后按照桶的顺序依次输出所有元素，从而得到全局有序序列。

桶排序的核心策略是"化整为零，分而治之"。与快速排序等基于比较的排序算法不同，桶排序利用数据本身的分布特征，将排序任务分解到多个桶中并行或串行处理。当待排序数据满足均匀分布条件时，桶排序可以达到近乎线性的时间复杂度，在某些场景下显著优于基于比较的排序算法。

桶排序的核心思想

数据分桶： 根据数据范围将元素映射到对应桶中
桶内排序： 对每个桶内部独立排序（可选用任意排序算法）
有序合并： 按照桶的顺序依次输出元素，得到全局有序序列

二、算法原理与流程

桶排序的执行过程可以直观地分为三个主要步骤，下面的流程图清晰展示了这一过程：

原始数组 → 初始化空桶 → 数据分桶 → 桶内排序 → 合并桶 → 有序数组

步骤一：初始化空桶

根据输入数据的范围与分布特征，确定桶的数量 bucketCount，并创建对应数量的空桶（通常用列表表示）。桶的数量选择直接影响排序性能，是桶排序中最为关键的参数之一。

步骤二：数据分桶

遍历待排序数组中的每个元素，根据映射函数将其分配到对应的桶中。映射函数通常为：

bucketIndex = floor((element - minValue) / range * bucketCount)

其中 range = maxValue - minValue + 1，即数据的取值范围。映射函数的核心作用是保证元素按大小顺序分布到不同的桶中，且桶之间的顺序就是元素的有序顺序。

步骤三：桶内排序

对每个非空桶内部的元素进行排序。桶内排序算法可以选择：

插入排序： 当桶内元素较少时效率最高，是桶排序最常用的搭配
快速排序： 桶内元素较多时更优，整体时间复杂度更稳定
递归桶排序： 对桶内数据继续分桶，适合数据量极大的场景

步骤四：合并桶

按照桶的索引顺序（从小到大），依次将所有桶内的元素拼接起来，得到全局有序的数组。

桶排序的精髓不在于排序本身，而在于如何"分"。好的分桶策略可以让每个桶内的数据量大致相等，从而使桶内排序的开销降到最低。当桶的数量接近数据规模时，桶排序退化为计数排序；当桶的数量为1时，桶排序退化为所选的桶内排序算法。

三、桶的数量选择与数据分布的影响

桶的数量对性能的影响

桶的数量是桶排序最关键的参数，直接影响算法的时间复杂度和空间复杂度：

桶数量	每个桶的平均元素数	时间复杂度	空间复杂度	适用场景
k = 1	n	退化为桶内排序算法	O(n)	退化为普通排序，不推荐
k = sqrt(n)	sqrt(n)	O(sqrt(n)) 每桶	O(n + sqrt(n))	空间与时间平衡
k = n	约 1	O(n)	O(2n)	均匀分布数据，最优
k = n * c	< 1	O(n)	O(n + k)	空间充裕时

数据分布对性能的影响

桶排序的性能高度依赖输入数据的分布特征：

均匀分布 -- 最佳情况

当数据在值域范围内均匀分布时，每个桶中的元素数量大致相等，桶内排序的开销最小。此时桶排序的平均时间复杂度可以达到 O(n + k)，当 k 约等于 n 时接近 O(n)。这是桶排序最理想的应用场景，例如对均匀分布的浮点数进行排序。

倾斜分布 -- 最差情况

当数据集中在很小的值域范围内时，大量元素会落入同一个桶中，导致桶内排序的开销剧增。最差情况下，所有元素都进入同一个桶，此时桶排序的时间复杂度完全取决于桶内排序算法。若桶内使用插入排序，最差时间复杂度为 O(n^2)。这是桶排序的主要局限性。

极端值的影响

少量远离主体数据范围的极端值（离群点）会导致桶的映射范围过大，使大量元素挤入少数桶中。解决方案是在分桶前对数据进行预处理，识别并分离极端值，或者使用动态分桶策略。

应对数据倾斜的策略

对数分桶： 对于呈指数分布的数据使用对数映射
自适应分桶： 根据数据分布动态调整桶边界
直方图分桶： 先对数据采样生成直方图，再确定桶边界
递归分桶： 对元素过多的桶递归应用桶排序

示例：不同分布下的表现

输入数据：[0.12, 0.34, 0.56, 0.78, 0.91, 0.23, 0.45, 0.67, 0.89, 0.01]（10个[0,1)均匀分布浮点数）

使用 k = 5 个桶，每个桶期望元素数 = 2。实际分布可能为 [2, 2, 2, 2, 2]，非常均衡，桶内排序开销极低。

输入数据：[0.01, 0.02, 0.03, 0.04, 0.05, 0.91, 0.92, 0.93, 0.94, 0.95]（聚集在两端的双峰分布）

使用 k = 5 个桶，桶0和桶4各有5个元素，桶1-3为空。桶内排序需处理5个元素，开销增大但仍在可控范围。

四、桶内排序策略的选择

桶内排序算法的选择直接影响桶排序的整体性能。不同的桶内排序策略在不同场景下各有优劣。下表总结了常用组合：

桶内排序	平均复杂度	最差复杂度	稳定性	推荐场景
插入排序	O(n/k)^2	O(n^2)	稳定	桶内元素少（< 50），数据基本均匀
快速排序	O(n/k log(n/k))	O((n/k)^2)	不稳定	桶内元素较多，需要稳定性能
归并排序	O(n/k log(n/k))	O(n/k log(n/k))	稳定	需要稳定排序，桶内元素较多
递归桶排序	O(n/k)	O((n/k)^2)	视实现而定	数据量大且分布均匀

插入排序 + 桶排序（经典组合）

经典的桶排序通常搭配插入排序作为桶内排序算法。原因是当桶的数量 k 接近 n 时，每个桶内的元素期望数量为常数（通常为 1~3 个），此时插入排序的实际运行速度极快，且实现简单、常数因子小。即使桶内有少量元素，插入排序在小规模数据上的表现也优于快速排序等复杂算法。

快速排序 + 桶排序

当无法保证数据均匀分布、桶内元素可能较多时，使用快速排序作为桶内排序可以保证更稳定的整体性能。这种做法在数据分布不确定的生产环境中更为常见。

递归桶排序

递归桶排序是对桶内元素再次应用桶排序，形成"桶中桶"的嵌套结构。当数据量极大且呈现多层分布特征时，递归策略可以有效减少每层的排序开销。递归深度通常由桶内元素的数量阈值决定，当桶内元素数量小于某个阈值时，切换为插入排序。

def bucket_sort_recursive(arr, bucket_count=10, threshold=16):
    # 递归桶排序，当桶内元素少于阈值时使用插入排序
    if len(arr) <= threshold:
        return insertion_sort(arr)

    if len(arr) == 0:
        return arr

    min_val, max_val = min(arr), max(arr)
    if min_val == max_val:
        return arr

    # 创建空桶
    buckets = [[] for _ in range(bucket_count)]
    range_size = max_val - min_val + 1

    # 数据分桶
    for num in arr:
        idx = int((num - min_val) / range_size * bucket_count)
        idx = min(idx, bucket_count - 1)
        buckets[idx].append(num)

    # 对每个桶递归排序并合并
    result = []
    for bucket in buckets:
        result.extend(bucket_sort_recursive(bucket, bucket_count, threshold))

    return result

五、时间复杂度与空间复杂度分析

时间复杂度

设待排序数据量为 n，桶的数量为 k，则桶排序的时间复杂度由以下部分组成：

数据分桶： O(n) -- 遍历一次所有元素，将其分配到对应桶中
桶内排序： 设第 i 个桶中的元素数量为 n_i，则桶内排序的总时间为 Σ O(n_i log n_i)（若使用比较排序）或 Σ O(n_i^2)（若使用插入排序）
合并桶： O(k) -- 遍历所有桶，依次输出元素

复杂度汇总

平均时间复杂度： O(n + k) 当数据均匀分布且桶内使用非比较排序时；对于基于比较的桶内排序为 O(n + k) * O(n/k log(n/k)) = O(n log(n/k))
最差时间复杂度： O(n^2) 或 O(n log n) 取决于桶内排序算法
最佳时间复杂度： O(n + k) 数据均匀分布且桶内元素为常数个
空间复杂度： O(n + k) 需要额外存储 n 个元素和 k 个桶

详细推导

在数据均匀分布的理想情况下，每个桶中的元素数量约为 n/k。若桶内使用插入排序，单桶排序时间为 O((n/k)^2)，总排序时间为：

T(n) = O(n) + k * O((n/k)^2) + O(k)
     = O(n) + O(n^2/k) + O(k)

当 k ≈ n 时，T(n) = O(n) + O(n) + O(n) = O(n)

当桶内使用基于比较的排序（如快速排序）时：

T(n) = O(n) + k * O((n/k) * log(n/k)) + O(k)
     = O(n) + O(n * log(n/k)) + O(k)

当 k ≈ n 时，log(n/k) ≈ 0，T(n) ≈ O(n)
当 k 为常数时，T(n) = O(n log n)

空间复杂度

桶排序的空间复杂度为 O(n + k)：

O(n) 用于存储所有元素本身（如果使用额外数组存放结果）
O(k) 用于存储 k 个桶的引用结构
若采用原地桶排序实现，可优化空间使用，但很少在实践中应用

桶排序是典型的非原地排序算法，这在内存敏感的环境中需要注意。

六、代码实现

Python 实现（经典版，桶内插入排序）

def bucket_sort(arr, bucket_count=10):
    """
    桶排序（桶内使用插入排序）

    参数:
        arr: 待排序数组（元素为 [0, 1) 范围内的浮点数）
        bucket_count: 桶的数量

    返回:
        排序后的数组
    """
    if len(arr) <= 1:
        return arr

    # 1. 创建空桶
    buckets = [[] for _ in range(bucket_count)]

    # 2. 将元素分配到桶中
    for num in arr:
        index = int(num * bucket_count)
        index = min(index, bucket_count - 1)
        buckets[index].append(num)

    # 3. 对每个桶内部进行排序（插入排序）
    for i in range(bucket_count):
        buckets[i] = insertion_sort(buckets[i])

    # 4. 合并所有桶
    result = []
    for bucket in buckets:
        result.extend(bucket)

    return result


def insertion_sort(arr):
    """插入排序（用于桶内排序）"""
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Java 实现（支持任意范围整数）

import java.util.*;

public class BucketSort {

    public static void bucketSort(int[] arr, int bucketCount) {
        if (arr == null || arr.length <= 1) return;

        // 找到最小值和最大值
        int minVal = arr[0];
        int maxVal = arr[0];
        for (int num : arr) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }

        // 创建桶
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 分桶
        double range = (double)(maxVal - minVal + 1);
        for (int num : arr) {
            int index = (int)((num - minVal) / range * bucketCount);
            index = Math.min(index, bucketCount - 1);
            buckets.get(index).add(num);
        }

        // 桶内排序
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket); // TimSort
        }

        // 合并
        int idx = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[idx++] = num;
            }
        }
    }
}

C++ 实现（指针版，高性能）

#include <vector>
#include <algorithm>
#include <cmath>

void bucketSort(std::vector<double>& arr, int bucketCount) {
    if (arr.size() <= 1) return;

    // 创建桶
    std::vector<std::vector<double>> buckets(bucketCount);

    // 分桶（假设数据范围为 [0, 1)）
    for (double num : arr) {
        int index = static_cast<int>(num * bucketCount);
        index = std::min(index, bucketCount - 1);
        buckets[index].push_back(num);
    }

    // 桶内排序
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
    }

    // 合并回原数组
    int idx = 0;
    for (const auto& bucket : buckets) {
        for (double num : bucket) {
            arr[idx++] = num;
        }
    }
}

JavaScript 实现（浏览器端）

function bucketSort(arr, bucketCount = 10) {
    if (arr.length <= 1) return arr;

    // 创建空桶
    const buckets = Array.from({ length: bucketCount }, () => []);

    // 分桶（假设 [0, 1) 浮点数）
    for (const num of arr) {
        const index = Math.min(
            Math.floor(num * bucketCount),
            bucketCount - 1
        );
        buckets[index].push(num);
    }

    // 桶内排序 + 合并
    const result = [];
    for (const bucket of buckets) {
        bucket.sort((a, b) => a - b);  // 插入排序或快排（引擎决定）
        result.push(...bucket);
    }

    return result;
}

七、计数排序 vs 桶排序 vs 基数排序

计数排序、桶排序、基数排序三者都属于非比较排序算法，但它们的核心思想和适用场景有显著差异。下表从多个维度进行系统对比：

对比维度	计数排序 (Counting Sort)	桶排序 (Bucket Sort)	基数排序 (Radix Sort)
核心思想	统计每个值出现的次数	将数据分到多个桶中	按位（个/十/百位）逐次排序
基础操作	计数 + 前缀和	分桶 + 桶内排序 + 合并	分配 + 收集（多趟）
时间复杂度	O(n + k)	O(n + k) 平均	O(d * (n + k))
空间复杂度	O(k)	O(n + k)	O(n + k)
稳定性	稳定	取决于桶内排序	稳定
数据要求	整数，值域范围小	均匀分布，浮点数	整数或定长字符串
桶/箱数量	k = max - min + 1	k 可任意指定	k = 基数（通常10或256）
敏感因素	值域范围	数据分布均匀性	数据位数（d）
典型应用	年龄排序、成绩排序	浮点数排序、大数据排序	整数排序、字符串排序

三者关系的关键认知

计数排序是桶排序的特例： 当桶排序的桶数量等于值域范围（k = max - min + 1）时，每个桶最多放一个元素，退化为计数排序
基数排序是桶排序的多次应用： 基数排序的每一趟分配-收集过程本质上就是一次桶排序，只不过桶的数量固定为基数（10或256）
空间上： 计数排序空间效率最高（只需计数数组），桶排序空间开销最大（需存储元素本身）
通用性： 基数排序适用性最广（可处理整数和字符串），桶排序对数据分布最敏感

选择建议

浮点数排序 -- 优先选择桶排序，因为浮点数的值域连续且通常呈现均匀分布，桶排序不需要将浮点数转化为整数。

小范围整数排序 -- 优先选择计数排序，实现简单且性能最优。

大范围整数/字符串排序 -- 优先选择基数排序，能在 O(n) 时间复杂度内完成排序。

数据分布不确定 -- 优先选择快速排序（基于比较），虽然复杂度 O(n log n) 但性能稳定。

八、稳定性分析

什么是排序稳定性

排序算法的稳定性是指：如果两个相等的元素在排序前后的相对位置保持不变，则称该排序算法是稳定的。稳定性在多关键字排序（如按分数排序后按姓名排序）场景中尤为重要。

桶排序的稳定性

桶排序的稳定性取决于桶内排序算法：

分桶阶段： 稳定的。相同元素会被映射到同一个桶中，且遍历顺序保持了原始顺序
桶内排序阶段： 若使用插入排序或归并排序，桶内排序是稳定的，整体算法稳定
桶内排序阶段： 若使用快速排序或堆排序，桶内排序是不稳定的，整体算法不稳定
合并阶段： 稳定的。按桶索引顺序依次输出，不改变桶内元素的相对顺序

保持稳定性的策略

若应用场景要求稳定排序（如数据库排序、多关键字排序），建议桶内排序使用插入排序或归并排序。在大多数教科书和经典实现中，桶排序默认搭配插入排序，因此通常被认为是一种稳定排序算法。

九、适用场景与工程实践

典型应用场景

1. 浮点数排序

桶排序最经典的应用场景是对 [0, 1) 范围内的浮点数进行排序。由于浮点数的均匀分布特性，桶排序可以在 O(n) 时间内完成排序。例如：对大量科学计算产生的浮点数据进行排序。

2. 大数据外部排序

当数据量远超内存容量时，桶排序的"分桶"思想天然适合外部排序。可以将每个桶存储到磁盘上的独立文件中，逐个加载到内存中排序后再合并。这在处理 TB 级别的日志数据时非常高效。

3. 均匀分布的历史数据

对于已知呈均匀分布的大规模数据集（如用户ID哈希值、传感器读数），桶排序可以发挥最佳性能。

4. 并行排序

桶排序天然适合并行化处理。分桶阶段可以并行统计元素归属；桶内排序阶段各桶完全独立，可以分配给不同的线程或进程并行执行。这是桶排序在当今多核时代的突出优势。

工程注意事项

桶数量的选取： 通常取 k = n / 10 到 k = n 之间，具体取决于数据分布和内存限制
内存开销： 所有元素需要额外存储一次，当内存受限时需谨慎使用
最差情况防护： 当检测到数据严重倾斜时，应切换到基于比较的排序算法作为 fallback
缓存局部性： 桶排序的随机写入特性可能导致较多的缓存缺失，对于超大规模数据需注意缓存优化

在实际工程中，桶排序常被用作混合排序策略的一部分。例如，Java 的 Arrays.sort() 在对浮点数数组排序时，会检测数据分布，在合适的情况下使用桶排序变体进行优化。Python 的 TimSort 虽然基于归并排序，但在某些场景下也会借鉴桶排序的分桶思想。

十、核心要点总结

桶排序要点速记

算法分类： 非比较排序、分布式排序，利用数据分布特征实现高效排序
三步流程： 初始化空桶 → 数据分桶 → 桶内排序 → 合并桶
时间复杂度： 平均 O(n + k)（均匀分布时接近线性），最差 O(n^2) 或 O(n log n)（取决于桶内排序）
空间复杂度： O(n + k)，非原地排序
稳定性： 取决于桶内排序算法，搭配插入排序时为稳定排序
关键参数： 桶的数量 k 的选择至关重要，k ≈ n 时性能最优
数据敏感： 性能高度依赖数据分布，均匀分布下表现最佳，倾斜分布下可能退化
三非比较排序关系： 计数排序是桶排序的特例，基数排序是桶排序的多次应用
最佳场景： 均匀分布浮点数排序、大数据外部排序、并行排序
工程建议： 搭配插入排序作为桶内算法 + 最差情况防护 fallback 机制

十一、进一步思考与实践

思考与练习

数据分布实验： 分别用均匀分布、正态分布、指数分布的数据测试桶排序的性能，观察桶数量对性能的影响曲线
混合排序实现： 实现一个自适应桶排序，能在检测到数据倾斜时自动切换到快速排序
并行版本： 使用多线程实现并行桶排序，比较不同桶内排序策略下的加速比
外部排序： 设计一个基于桶排序的外部排序方案，处理无法一次性装入内存的超大规模数据
计数排序退化验证： 实现当 k = max - min + 1 时的特殊桶排序，验证其行为是否与计数排序一致

扩展阅读

《算法导论（CLRS）》第8章 -- 线性时间排序的完整理论推导
《算法（第4版）》Sedgewick -- 桶排序的实际工程实现
MSD Radix Sort -- 结合了桶排序和基数排序思想的变体
Proxmap Sort -- 桶排序的变种，通过逼近映射优化分桶策略