C++桶排序教程

桶排序（Bucket Sort）是一种高效的排序算法，特别适合处理均匀分布的数据。它的核心思想是将数据分到多个桶中，每个桶内部再进行排序，最后合并所有桶的结果。

1. 桶排序基本原理

桶排序的工作流程如下：

1. 分桶：将数据根据映射函数分配到不同的桶中
2. 桶内排序：对每个桶内的数据单独排序（可使用其他排序算法）
3. 合并：按顺序将所有桶的结果合并

2. 桶排序实现代码

下面是桶排序的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 桶排序函数
void bucketSort(vector<double>& arr) {
    int n = arr.size();
    if (n <= 0) return;
    
    // 1. 确定最大值和最小值，用于分桶
    double max_val = arr[0];
    double min_val = arr[0];
    for (double num : arr) {
        if (num > max_val) max_val = num;
        if (num < min_val) min_val = num;
    }
    
    // 2. 创建桶
    int bucketCount = n; // 桶的数量，通常取数组大小
    vector<vector<double>> buckets(bucketCount);
    
    // 3. 将元素分配到桶中
    for (double num : arr) {
        // 映射函数：确定元素应该放入哪个桶
        int bucketIndex = (int)((num - min_val) / (max_val - min_val) * (bucketCount - 1));
        buckets[bucketIndex].push_back(num);
    }
    
    // 4. 对每个桶进行排序
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
    }
    
    // 5. 合并所有桶的结果
    int index = 0;
    for (const auto& bucket : buckets) {
        for (double num : bucket) {
            arr[index++] = num;
        }
    }
}

int main() {
    // 测试数据
    vector<double> arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
    
    cout << "排序前: ";
    for (double num : arr) {
        cout << num << " ";
    }
    cout << endl;
    
    // 执行桶排序
    bucketSort(arr);
    
    cout << "排序后: ";
    for (double num : arr) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

3. 桶排序代码解释

核心步骤分析：

1. 确定数据范围：

   double max_val = arr[0];
   double min_val = arr[0];
   for (double num : arr) {
       if (num > max_val) max_val = num;
       if (num < min_val) min_val = num;
   }
   

   • 这一步计算数组的最大值和最小值，用于后续分桶

2. 创建桶并分配元素：

   int bucketCount = n;
   vector<vector<double>> buckets(bucketCount);
   
   for (double num : arr) {
       int bucketIndex = (int)((num - min_val) / (max_val - min_val) * (bucketCount - 1));
       buckets[bucketIndex].push_back(num);
   }
   

   • 映射函数 (num - min_val) / (max_val - min_val) * (bucketCount - 1) 确保元素被均匀分配到桶中

3. 桶内排序与合并：

   for (auto& bucket : buckets) {
       sort(bucket.begin(), bucket.end());
   }
   
   int index = 0;
   for (const auto& bucket : buckets) {
       for (double num : bucket) {
           arr[index++] = num;
       }
   }
   

   • 使用STL的sort函数对每个桶内部进行排序
   • 按顺序合并所有桶的元素，完成排序

4. 桶排序的时间复杂度

桶排序的时间复杂度分析：

• 平均情况：O(n + k)，其中n是元素数量，k是桶的数量
• 最坏情况：O(n²)，当所有元素都分配到同一个桶时
• 空间复杂度：O(n + k)，需要额外的桶空间

5. 桶排序的适用场景

桶排序适合以下场景：

• 数据均匀分布在某个范围内
• 数据范围不是特别大
• 需要稳定的排序算法

6. 处理整数数据的桶排序

如果需要对整数进行桶排序，可以这样修改映射函数：

// 处理整数的桶排序
void bucketSortInt(vector<int>& arr) {
    int n = arr.size();
    if (n <= 0) return;
    
    // 确定最大值和最小值
    int max_val = arr[0];
    int min_val = arr[0];
    for (int num : arr) {
        if (num > max_val) max_val = num;
        if (num < min_val) min_val = num;
    }
    
    // 创建桶
    int bucketCount = (max_val - min_val) / n + 1; // 动态确定桶数量
    vector<vector<int>> buckets(bucketCount);
    
    // 将元素分配到桶中
    for (int num : arr) {
        int bucketIndex = (num - min_val) / n;
        buckets[bucketIndex].push_back(num);
    }
    
    // 对每个桶进行排序并合并结果
    arr.clear();
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
        arr.insert(arr.end(), bucket.begin(), bucket.end());
    }
}

7. 桶排序的优缺点

优点：

• 时间复杂度接近线性，效率高
• 适用于浮点数等特殊数据类型
• 稳定性好（取决于桶内排序算法）

缺点：

• 需要额外的空间
• 对数据分布敏感，分布不均匀时性能下降
• 实现相对复杂，需要合理设计映射函数

8. 总结

桶排序是一种高效的排序算法，但对数据分布有一定要求。在实际应用中，需要根据数据特点选择合适的映射函数和桶数量。当数据均匀分布时，桶排序可以达到接近线性的时间复杂度，是一种非常高效的选择。

#include<iostream>
using namespace std;
int tong[100];//={};//有一个整数序列，在[0,100]
int main() {
	int n;
	cin >> n;
	int Max = 0;
	int Min = 100;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		tong[a] += 1;
		Max = max(Max,a);
		Min = min(Min,a);
	}
	
	for(int i=Min;i<=Max;i++){
		cout<<i<<"\t";
	}
	puts("");
	for(int i=Min;i<=Max;i++){
		cout<<tong[i]<<"\t";
	}
	return 0;
}