桶排序 C++ 学习笔记教程

一、开篇总览

桶排序是一种巧妙的排序算法，核心思路是利用“桶”（数组）的下标天然有序的特性，把待排序数据按规则放进对应桶里，再按桶顺序输出实现排序 。尤其适合数据范围有限的场景，还能顺带解决去重、计数问题，下面一步步拆解学习。

二、桶排序核心原理（以正数范围为例）

（一）原理通俗讲

假设要排序的数据是 1、2、3、2、3、5、1、5、2、3 ，数据范围是 1 - 5 。我们创建一个长度能覆盖该范围的数组（桶），初始值全为 0 。遍历待排序数据，遇到数字几，就把对应桶（数组下标为该数字）的计数加 1 。最后从下标 1 到 5 遍历桶，下标对应的值是几，就输出几次下标，就能得到有序序列啦，像这样：

原始数据：1 2 3 2 3 5 1 5 2 3 
桶数组初始：[0, 0, 0, 0, 0, 0]（下标 0 不用，关注 1 - 5 ）
遍历数据后桶数组：[0, 2, 3, 3, 0, 2]（下标 1 对应值 2，说明数字 1 出现 2 次；下标 2 对应值 3，说明数字 2 出现 3 次 ，以此类推） 
按桶输出：1 1 2 2 2 3 3 3 5 5 

（二）代码示例（基础排序）

#include<iostream>
using namespace std;

int main() {
    // 假设数据范围是 1 - 1000，创建桶数组，初始化为 0
    int tong[1001] = {0}; 
    int n;
    cin >> n; // 输入数据个数
    for (int i = 0; i < n; i++) { 
        int x;
        cin >> x; 
        tong[x]++; // 对应桶计数加 1，实现“唱票”
    }
    // 按桶下标顺序输出，下标就是数据，值是出现次数
    for (int i = 1; i <= 1000; i++) { 
        for (int j = 0; j < tong[i]; j++) { 
            cout << i << " "; 
        }
    }
    return 0;
}

代码注释：

• int tong[1001] = {0}; ：定义桶数组，下标 0 - 1000 ，覆盖数据范围 1 - 1000 ，初始全 0 。
• tong[x]++; ：遇到数据 x ，对应下标 x 的桶计数加 1 ，记录 x 出现次数。
• 外层 for (int i = 1; i <= 1000; i++) 遍历桶下标（即可能的数据值），内层 for (int j = 0; j < tong[i]; j++) 根据桶计数，决定输出几次当前下标，实现排序输出。

三、处理包含负数的桶排序

（一）问题分析

当数据包含负数，比如范围 -1000 ~ 1000 ，直接用负数当下标会报错。解决方案是偏移量处理：给每个数加上一个偏移值（如 1000 ），把负数范围映射到非负范围（0 ~ 2000 ），排完序后再减回去。

（二）代码示例（含负数排序，从大到小输出）

#include<iostream>
using namespace std;

int main() {
    // 数据范围 -1000~1000，加 1000 后映射到 0~2000，创建对应长度桶数组
    int a[2001] = {0}; 
    int n, t;
    cin >> n; 
    for (int i = 1; i <= n; i++) { 
        cin >> t; 
        // 加 1000 偏移，让负数也能作为合法下标
        a[t + 1000]++; 
    }
    // 从大到小遍历桶（下标 2000 对应原数 1000，下标 0 对应原数 -1000 ）
    for (int i = 2000; i >= 0; i--) { 
        for (int j = 1; j <= a[i]; j++) { 
            // 输出时减 1000 还原原数
            cout << i - 1000 << " "; 
        }
    }
    return 0;
}

代码注释：

• int a[2001] = {0}; ：因数据范围 -1000~1000 ，共 2001 个数（含 0 ），创建长度 2001 的桶数组。
• a[t + 1000]++; ：给输入的数 t 加 1000 ，让负数（如 -1000 ）变成 0 ，正数（如 1000 ）变成 2000 ，都能作为数组下标。
• for (int i = 2000; i >= 0; i--) ：从最大偏移后下标（对应原数 1000 ）往最小（对应原数 -1000 ）遍历，实现从大到小排序。
• cout << i - 1000 << " "; ：输出时减去偏移量，还原原始数据。

四、桶排序的去重应用（以年龄去重排序为例）

（一）需求分析

学校统计师生年龄，要按从小到大排序，且重复年龄只保留一个。利用桶排序，只要桶里计数大于 0 ，就输出一次下标（年龄），就能实现去重 + 排序。

（二）代码示例（年龄去重排序）

#include<iostream>
using namespace std;

int main() {
    // 年龄不超 100 岁，创建桶数组覆盖 1 - 100
    int a[101] = {0}; 
    int n, t;
    cin >> n; 
    for (int i = 1; i <= n; i++) { 
        cin >> t; 
        a[t]++; // 对应年龄计数加 1
    }
    // 遍历年龄范围，桶计数 >0 就输出下标（年龄），实现去重排序
    for (int i = 1; i <= 100; i++) { 
        if (a[i] > 0) { 
            cout << i << " "; 
        }
    }
    return 0;
}

代码注释：

• int a[101] = {0}; ：年龄范围假设 1 - 100 ，创建长度 101 的桶数组（下标 0 不用 ）。
• a[t]++; ：记录每个年龄 t 出现的次数。
• if (a[i] > 0) ：只要该年龄对应的桶计数大于 0 ，说明有这个年龄，输出一次下标 i （即年龄），实现去重且按从小到大排序（因遍历顺序是 1 - 100 ）。

五、桶排序的计数应用（拓展）

结合前面基础排序代码，遍历桶数组时，输出 i << "：" << tong[i] ，就能得到每个数字出现的次数，比如：

// 基于基础排序代码，添加计数输出
cout << "计数结果：" << endl;
for (int i = 1; i <= 1000; i++) {
    if (tong[i] != 0) {
        cout << i << " 出现了 " << tong[i] << " 次" << endl;
    }
}

这样就能用桶排序同时完成排序、计数，是不是很方便！

六、总结

桶排序关键在于利用数据范围设计桶数组，通过下标对应数据、值记录出现次数，实现排序、去重、计数。处理负数时用偏移量映射范围，遇到不同场景（如年龄去重），调整桶大小和输出逻辑即可。学会它，处理有限范围数据的排序问题就轻松啦，快去用代码试试不同场景吧 ～