数据结构：桶排序 (Bucket Sort)

闪电麦坤705

1192人浏览 · 2025-09-02 08:38:30

闪电麦坤705 · 2025-09-02 08:38:30 发布

第二步：实现“分发 (Scatter)”过程

第三步：对每个桶进行内部排序

第四步：合并结果 (Gather)

复杂度与特性分析

时间复杂度 (Time Complexity)

空间复杂度 (Space Complexity)

稳定性 (Stability)

我们来探讨一种非常强大的排序算法——桶排序 (Bucket Sort)，它也被称为箱排序 (Bin Sort)。这个算法可以看作是之前我们讨论的计数排序的一种泛化和升级。

从“精确计数”到“分而治之”的升维

我们先回顾一下计数排序的巨大优点和它的致命弱点：

优点：通过“值->索引”的映射，实现了惊人的 O(n+k) 线性时间排序。
弱点：
1. 它只能处理整数。
2. 如果整数范围 k 极大（比如要排序 [1, 1000, 999999]），就需要一个极大的 count 数组，造成巨大的空间浪费。

那么，我们能否保留其“按值分配”的核心思想，同时克服这两个弱点呢？

核心思想的升维：

计数排序是为每一个可能的值都准备一个“坑位”。桶排序则放宽了这个条件：我们不为每个值准备坑位，而是准备有限个“桶 (Bucket)”，每个桶负责一个值的范围 (range)。

这个思想源于一个非常符合直觉的“分而治之”策略：

1️⃣分发 (Scatter)：想象一下，有一大堆考试试卷，分数范围从0到100。我们可以先准备10个大箱子，分别贴上标签“0-9分”、“10-19分”、“20-29分”……然后我们遍历所有试卷，根据分数把它们扔进对应的箱子里。

2️⃣ 征服 (Conquer)：现在，那个巨大的、难以处理的排序问题，被我们分解成了10个规模小得多的子问题。我们只需要对每个箱子内部的试卷进行单独排序。因为每个箱子里的试卷数量有限，排序会快得多。

3️⃣ 合并 (Gather)：当所有箱子内部都排好序后，我们再按照箱子的顺序（0-9分的箱子，然后10-19分的箱子……），依次把里面的试卷拿出来拼接在一起。最终的结果，必然是完全有序的。

这个“分发 -> 内部排序 -> 合并”的过程，就是桶排序的第一性原理。它将一个大范围的排序问题，转化为了多个小范围的排序问题。

如何设计“桶”和“分发”规则

📌 核心问题：给定一个元素，如何快速确定它应该被放入哪个桶？

我们需要一个映射函数，能将输入的值域映射到桶的索引。为了讲解方便，我们做一个经典假设：

输入数据是均匀分布在 [0, 1) 区间内的浮点数。

创建桶：我们决定创建 k 个桶（k 通常取一个合理的数，比如10）。在代码中，我们可以用一个数组来表示这些桶。

但每个桶里要放多少元素是不确定的，所以每个桶本身必须是一个能动态增长的结构。在没有STL的情况下，链表是实现这个功能的经典选择。

设计映射函数：我们要将 [0, 1) 的浮点数，映射到 [0, k-1] 的桶索引。最简单的函数就是：

bucket_index = floor(k * element_value)

例如，有10个桶 (k=10)，元素值为 0.78。floor(10 * 0.78) = floor(7.8) = 7。所以 0.78 应该放入第7号桶（索引从0开始）。
元素值为 0.12。floor(10 * 0.12) = floor(1.2) = 1。它应该放入第1号桶。

代码的逐步完善

第一步：定义数据结构和初始化桶

因为不能用STL的vector，我们需要自己定义一个链表节点来作为桶内的数据结构。

#include <iostream>

// 用来构成每个桶的链表节点
struct Node {
    float data;
    Node* next;
};

// 桶排序函数框架
void bucketSort(float arr[], int n) {
    // 1. 创建桶
    //    为简化，我们创建10个桶
    const int num_buckets = 10;
    Node* buckets[num_buckets];

    // 2. 初始化所有桶为空（即链表头指针为 nullptr）
    for (int i = 0; i < num_buckets; i++) {
        buckets[i] = nullptr;
    }

    // ... 后续步骤将在这里展开 ...
}

第二步：实现“分发 (Scatter)”过程

我们需要遍历原数组，将每个元素放入计算出的桶中。我们需要一个简单的函数来将新元素添加到链表的头部。

// (接上)

// 辅助函数：将一个新元素添加到链表的头部
void push(Node** head_ref, float new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    //让新节点的next指针指向当前的头节点
    new_node->next = (*head_ref);
    //将链表的头指针指向新创建的节点
    (*head_ref) = new_node;
}

void bucketSort(float arr[], int n) {
    // ... (初始化桶的代码) ...

    // 3. 分发元素到各个桶中
    for (int i = 0; i < n; i++) {
        // 计算元素 arr[i] 应该去的桶的索引
        int bucket_idx = num_buckets * arr[i]; 
        
        // 将 arr[i] 放入对应的桶（链表）
        push(&buckets[bucket_idx], arr[i]);
    }

    // ... 后续步骤将在这里展开 ...
}

Node** head_ref：指向链表头指针的指针（二级指针）

为什么需要二级指针？

因为需要修改调用函数中的头指针值，而不仅仅是修改指针指向的内容。

第三步：对每个桶进行内部排序

现在数据已经分发完毕，我们需要遍历每个桶，对其中的链表进行排序。如何对链表排序？

插入排序是一个非常好的选择，因为它对于小规模或者基本有序的数据效率很高，并且实现相对简单。

// (我们需要一个对链表进行插入排序的辅助函数)
// 这个函数比较复杂，我们先假设它已经写好
void insertionSortList(Node** head_ref); // 函数声明

void bucketSort(float arr[], int n) {
    // ... (初始化和分发的代码) ...

    // 4. 对每一个桶（链表）进行排序
    for (int i = 0; i < num_buckets; i++) {
        insertionSortList(&buckets[i]);
    }

    // ... 后续步骤将在这里展开 ...
}

（为保持主逻辑清晰，insertionSortList 的具体实现我们暂不展开，但它的作用就是将一个无序链表变为有序链表。）

第四步：合并结果 (Gather)

所有桶内都已经排好序，现在我们只需要按顺序遍历所有桶，将元素依次拷贝回原数组。

void bucketSort(float arr[], int n) {
    // ... (初始化、分发、内部排序的代码) ...

    // 5. 从所有桶中收集元素，放回原数组
    int index = 0;
    for (int i = 0; i < num_buckets; i++) {
        Node* current = buckets[i];
        while (current != nullptr) {
            arr[index++] = current->data;
            current = current->next;
        }
    }
    
    // 在一个完整的程序中，我们还需要释放所有链表节点的内存
}