C/C++语言八大排序算法之桶排序全过程示例详解

什么是桶排序

桶排序（Bucket Sort）是一种线性排序算法，它的基本思想是将数组内的元素根据某个规则分配到若干个桶中，然后对每个桶内的元素进行排序，最终合并每个桶内的有序元素即可得到原数组的有序结果。

桶排序的主要应用场景是待排序元素的分布比较均匀的情况下，性能表现优于其他排序算法（例如快速排序、归并排序等）。桶排序的时间复杂度为 $O(n)$。

桶排序的基本思想

假设我们要对一个 $n$ 个数的数组进行排序，且这 $n$ 个数分布在区间 $[0,1)$ 上，我们可以将这个区间划分成 $n$ 个大小相等的子区间（桶），然后将 $n$ 个元素分别放入桶中。对于每个桶中的元素再进行排序，最终可以得到一个有序的序列。具体流程如下：

1. 创建一定数量的桶，编号为 $0$ 到 $n-1$。
2. 将待排序数组内的元素按照某种规律分配到各个桶中去。
3. 对于每个桶内的元素进行排序，可以使用其他排序算法，例如插入排序、快速排序等。
4. 合并每个桶内排序好的元素。

我们来看一个示例。假设我们有如下 $10$ 个数需要进行排序：

0.35, 0.21, 0.67, 0.89, 0.42, 0.15, 0.52, 0.71, 0.62, 0.99

我们将这 $10$ 个数分配到 $10$ 个大小相等的桶中去，例如第 $i$ 个桶中存放的是在 $[(i-1)/10, i/10)$ 区间内的数。

Bucket 0: 
Bucket 1: 0.15, 0.21
Bucket 2: 0.35
Bucket 3: 0.42
Bucket 4: 0.52
Bucket 5: 0.62
Bucket 6: 0.67, 0.71
Bucket 7: 
Bucket 8: 0.89
Bucket 9: 0.99

然后对于每个桶内的元素进行排序，例如使用插入排序进行排序。

Bucket 0: 
Bucket 1: 0.15, 0.21 <-- Insertion Sort
Bucket 2: 0.35 <-- Insertion Sort
Bucket 3: 0.42 <-- Insertion Sort
Bucket 4: 0.52 <-- Insertion Sort
Bucket 5: 0.62 <-- Insertion Sort
Bucket 6: 0.67, 0.71 <-- Insertion Sort
Bucket 7: 
Bucket 8: 0.89 <-- Insertion Sort
Bucket 9: 0.99 <-- Insertion Sort

最后合并每个桶内排序好的元素，即可得到一个有序的序列。

排序后的序列为：

0.15, 0.21, 0.35, 0.42, 0.52, 0.62, 0.67, 0.71, 0.89, 0.99

桶排序的示例代码

下面是使用桶排序对一个整型数组进行排序的示例代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void bucketSort(vector<int>& nums) {
    int n = nums.size();

    // 创建桶
    vector<vector<int>> buckets(n);

    // 将元素分配到桶中
    for (int i = 0; i < n; ++i) {
        int index = nums[i] / n;
        buckets[index].push_back(nums[i]);
    }

    // 对每个桶内的元素进行排序
    for (int i = 0; i < n; ++i) {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // 合并每个桶内排序后的元素
    int index = 0;
    for (auto bucket : buckets) {
        for (auto num : bucket) {
            nums[index++] = num;
        }
    }
}

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    bucketSort(nums);
    for (auto num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

输出：

1 1 2 3 3 4 5 5 5 6 9

桶排序的时间复杂度

创建桶的时间复杂度为 $O(n)$，将元素分配到桶中的时间复杂度为 $O(n)$，对每个桶内的元素进行排序的时间复杂度为 $O(kn\log n)$，其中 $k$ 为桶的数量，总体时间复杂度为 $O(kn\log n)$。当 $k$ 足够小的时候，桶排序的性能表现非常优秀，可以达到线性时间复杂度 $O(n)$。但当 $k$ 较大时，桶排序的性能表现会退化为 $O(n\log n)$。