零基础通俗易懂 桶排序完整教程（C++）

💡前置说明

适用人群：C++初学、信奥入门；只需掌握：数组+for循环 算法特点：数据范围固定且较小时，排序最快，比冒泡/选择排序高效很多 核心口诀：下标存数字，数组记次数，按序遍历输出

一、通俗原理（大白话）

1. 把数组当做一排带编号的木桶
   • 数组下标 = 木桶编号（对应要排序的数字）
   • 数组数值 = 这个数字出现的次数
2. 执行流程 ① 准备空木桶（定义数组，全局数组默认全部初始化为0，无需手动清零） ② 遍历所有数据，数字是几，就往几号桶丢一个球（对应下标计数+1） ③ 按顺序遍历木桶，读出桶内数据，天然形成有序序列

二、桶排序4大固定步骤（所有题目通用）

1. 确定数据最大/最小值，定义合适大小的桶数组
2. 读取全部数据，完成入桶计数
3. 根据需求选择遍历顺序：升序/降序、去重/保留重复
4. 遍历桶数组，输出排序结果

三、入门题型1：基础去重排序（年龄排序）

题目

输入n个年龄，从小到大排序，去掉重复数据输出 样例输入： 6 6 8 8 7 7 6 样例输出：6 7 8

逐行注释代码

#include<iostream>                 // 导入输入输出库，支持cin/cout
using namespace std;              // 启用标准命名空间，省略std::前缀
int bucket[200];                  // 定义桶数组，覆盖0-199年龄；全局变量默认全0
int main(){
    int n, x;                     // n：数据总数，x：临时存储读取的数字
    cin >> n;                     // 读取第一行：数据个数n
    for(int i = 1; i <= n; i++){  // 循环n次，读取所有输入数据
        cin >> x;                 // 读取单个年龄数据
        bucket[x]++;              // 核心代码：x号桶计数+1，记录数字出现
    }
    // 从小到大遍历桶，实现升序+去重
    for(int i = 0; i <= 199; i++){
        if(bucket[i] > 0){        // 判断：这个数字出现过
            cout << i << " ";     // 只输出一次，自动去重
        }
    }
    return 0;                     // 程序正常结束
}

四、入门题型2：常规排序（保留重复数据）

题目

1~10000范围内正整数，全部排序，保留重复数字 样例输入： 6 87 84 91 90 99 95 样例输出：84 87 90 91 95 99

逐行注释代码

#include<iostream>
using namespace std;
int bucket[10005];                // 桶数组：覆盖1~10000全部数字
int main(){
    int n, x;
    cin >> n;
    // 第一步：数据入桶计数
    for(int i = 1; i <= n; i++){
        cin >> x;
        bucket[x]++;
    }
    // 第二步：升序遍历，保留重复数字
    for(int i = 1; i <= 10000; i++){
        // 数字出现几次，就打印几次
        for(int j = 1; j <= bucket[i]; j++){
            cout << i << " ";
        }
    }
    return 0;
}

五、重难点：负数桶排序（偏移量用法）

核心知识点

数组下标不能是负数！ 解决方法：加偏移量平移数据 例：数据范围 -1000 ~ 1000 → 全部+1000，映射为 0~2000合法下标 输出时减去偏移量，还原原始负数

题目

-1000~1000整数，从大到小降序排序，保留重复 样例输入： 6 87 -84 91 90 99 95 样例输出：99 95 91 90 87 -84

逐行注释代码

#include<iostream>
using namespace std;
const int OFFSET = 1000;          // 定义偏移量常量，方便修改
int bucket[2001];                 // 映射后下标范围：0~2000
int main(){
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x;
        // 负数平移：原始数字+偏移量，转为正数下标
        bucket[x + OFFSET]++;
    }
    // 倒序遍历桶：实现从大到小排序
    for(int i = 2000; i >= 0; i--){
        for(int j = 1; j <= bucket[i]; j++){
            cout << i - OFFSET << " "; // 减去偏移量，还原原始数字
        }
    }
    return 0;
}

六、拓展题型：桶排序计数查询

题目

输入n个分数，k次查询，输出每个分数的人数

逐行注释代码

#include<iostream>
using namespace std;
int bucket[101];                  // 分数0~100，定义对应桶
int main(){
    int n, k, score;
    cin >> n >> k;                // 读取数据总数、查询次数
    for(int i = 1; i <= n; i++){
        cin >> score;
        bucket[score]++;          // 统计每个分数人数
    }
    for(int i = 1; i <= k; i++){
        cin >> score;
        cout << bucket[score]<<" ";// 直接读取桶内结果输出
    }
    return 0;
}

七、必考总结+易错点（做题必看）

1. 三种输出模式区别

✅ 去重排序：单层循环 + if判断（有数据只输出1次） ✅ 保留重复排序：双层for循环（按次数重复输出） ✅ 降序排序：从大到小遍历桶下标

2. 高频易错点

1. 局部数组不会自动清零！桶数组一律定义在main函数外面（全局），默认全0
2. 出现负数必须加偏移量平移，不能直接当下标
3. 桶排序只适合：数据范围小、数值为整数；数据跨度极大不能用
4. 偏移量 = 数据最小值的绝对值

3. 算法优缺点

✅ 优点：代码简单、排序速度最快、自带去重+计数功能 ❌ 缺点：数据范围过大时，浪费内存，无法使用