桶排序学习教程

一、什么是桶排序

同学们，想象一下我们要整理一堆彩色的珠子，有红色、蓝色、绿色等。桶排序呢，就像是我们准备几个不同颜色的桶，把相同颜色的珠子放进对应的桶里，最后按顺序把桶里的珠子倒出来，这样珠子就排好序啦。

在计算机里，当我们要给一组数字排序时，如果这些数字在一个不大的范围里，就可以用桶排序。就是用数组下标对应要排序的数值，把数字放进和它数值对应的“桶”（数组元素）里，最后按顺序输出桶里的内容，就能得到排好序的结果啦。

二、桶排序的准备知识

（一）数组的简单理解

数组就像一排小格子，每个格子有自己的编号（下标），可以用来存放东西。比如int tong[100]; ，这里的tong就是一个有100个小格子的数组，编号从0到99 ，能用来存整数。

（二）循环的简单理解

循环就像我们重复做一件事。比如for (int i = 1; i <= n; i++) ，就是让计算机从1开始，一直做到n ，重复执行大括号里的内容，就像我们重复数珠子、放珠子一样。

三、简单桶排序示例（正数范围排序）

（一）需求

假设我们要给几个在0到50之间的整数排序，用桶排序来做。

（二）代码实现及注释

#include<iostream>
using namespace std;

int main() {
    // 定义一个数组list，用来存待排序的数，最多能存500个
    int list[500]; 
    // n用来存我们要排序的数的个数，这些数在0到50之间
    int n; 
    // 定义桶数组tong，大小是100，初始化为0，每个元素对应一个可能的数值（0 - 99，这里我们用0 - 50）
    int tong[100] = {}; 

    // 输入要排序的数的个数n
    cin >> n; 
    for (int i = 1; i <= n; i++) { 
        // 循环n次，每次输入一个数到list数组里
        cin >> list[i]; 
        // 把当前数作为桶数组的下标，对应的桶里的计数加1，相当于把数放进对应的桶
        tong[list[i]]++; 
    }

    // 从0到50遍历桶数组
    for (int i = 0; i <= 50; i++) { 
        // 桶里有东西（计数大于0），就把对应的数值i输出
        if (tong[i] != 0) { 
            cout << i << " ";
        }
    }

    return 0;
}

（三）代码解释

1. 数组定义：int list[500]; 准备存要排序的数；int tong[100] = {}; 是桶数组，初始都为0，每个位置对应一个可能的数值（这里0 - 50 ），用来计数每个数出现的次数。
2. 输入数据：cin >> n; 输入要排序的数的个数，然后通过for循环输入每个数到list里，同时把数对应的桶的计数加1，就像把珠子放进对应颜色的桶。
3. 输出排序结果：再通过for循环遍历桶数组，只要桶里计数不为0，就输出对应的数值，这样输出的就是排好序的结果啦，因为是按桶的下标顺序（也就是数值从小到大）输出的。

四、桶排序处理去重和计数

（一）去重

还是用上面的例子，桶排序做去重很简单。当我们把数放进桶里后，只要桶里计数大于0，就输出一次对应的数值，这样重复的数就只会输出一次啦。就像前面代码里的if (tong[i] != 0) { cout << i << " "; } ，不管这个数原来出现多少次，只输出一次，就去掉重复的了。

以下是使用桶排序实现去重功能的C++代码，我添加了详细注释以便理解：

#include <iostream>
using namespace std;

int main() {
    // 待排序数组（可修改为其他测试数据）
    int data[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(data) / sizeof(data[0]); // 计算数组长度
    
    // 假设数据范围是0~100，创建对应桶数组并初始化为0
    const int MAX = 100;
    int bucket[MAX + 1] = {0};
    
    // 遍历数据，将每个数对应的桶位置置为1（标记存在）
    for (int i = 0; i < n; i++) {
        bucket[data[i]] = 1;
    }
    
    // 输出所有存在的数（即桶中值为1的下标）
    cout << "去重后的数为：";
    for (int i = 0; i <= MAX; i++) {
        if (bucket[i] == 1) {
            cout << i << " ";
        }
    }
    
    return 0;
}

代码说明：

1. 数据准备：

   • data[] 是待去重的数组，可根据需要修改
   • n 是数组长度，通过 sizeof 自动计算

2. 桶数组初始化：

   • bucket[MAX + 1] 用于标记每个数是否存在
   • 初始化为全0，表示所有数都不存在

3. 标记存在的数：

   • 遍历原数组，将每个数对应的桶位置置为1
   • 例如：遇到数字5，则 bucket[5] = 1

4. 输出去重结果：

   • 遍历桶数组，输出所有值为1的下标
   • 由于桶数组是按顺序遍历的，输出结果自然有序

示例运行：

对于输入数据 {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}，程序将输出：

去重后的数为：1 2 3 4 5 6 9

适用范围：

• 数据范围较小（如0~100）
• 所有数据都是非负整数
• 需要有序去重结果

如果数据范围较大或包含负数，可以适当调整桶数组的大小和偏移量。

（二）计数

如果我们想知道每个数出现多少次，也很容易。还是看桶数组里的计数，比如tong[3] 的值，就是数字3出现的次数。我们可以在输出排序结果的时候，把计数也输出来，像这样改改代码：

#include<iostream>
using namespace std;

int main() {
    int list[500]; 
    int n; 
    int tong[100] = {}; 

    cin >> n; 
    for (int i = 1; i <= n; i++) { 
        cin >> list[i]; 
        tong[list[i]]++; 
    }

    for (int i = 0; i <= 50; i++) { 
        if (tong[i] != 0) { 
            // 先输出数值，再输出出现的次数
            cout << i << " 出现了 " << tong[i] << " 次" << endl; 
        }
    }

    return 0;
}

这样就能知道每个数出现多少次啦，就完成计数任务了。

五、桶排序处理包含负数的情况

（一）需求

现在有个数可能是负数啦，比如范围在 -1000到1000之间，要给这些数从大到小排序，用桶排序怎么做呢？

（二）思路

因为数组下标不能是负数呀，所以我们可以想办法把负数“变”成正数。比如数的范围是 -1000到1000，那我们给每个数都加上1000，这样原来的 -1000就变成0，1000就变成2000，这样就可以用下标0到2000的数组来当桶啦。最后输出的时候，再把加上的1000减回去，就得到原来的数啦。

（三）代码实现及注释

#include<iostream>
using namespace std;

int main() {
    // 定义桶数组a，大小2001，因为-1000到1000共2001个数（包括-1000和1000）
    int a[2001] = {}; 
    int n, t; 

    // 输入要排序的数的个数n
    cin >> n; 
    for (int i = 1; i <= n; i++) { 
        // 输入每个数到t里
        cin >> t; 
        // 把数t加上1000，作为桶数组的下标，计数加1
        a[t + 1000]++; 
    }

    // 从大到小遍历桶数组（下标2000到0）
    for (int i = 2000; i >= 0; i--) { 
        // 桶里有几个数，就输出几次
        for (int j = 1; j <= a[i]; j++) { 
            // 输出的时候把加上的1000减回去，得到原来的数
            cout << i - 1000 << " "; 
        }
    }

    return 0;
}

（四）代码解释

1. 数组定义：int a[2001] = {}; 因为要处理 -1000到1000的数，每个数加1000后范围是0到2000，所以数组大小设为2001 。
2. 输入数据并处理：输入数的个数n和每个数t，把t加1000后作为桶数组的下标，对应桶的计数加1，这样就把负数也合理存到桶里啦。
3. 输出排序结果：从下标2000（对应原来的1000）往0（对应原来的 -1000）遍历桶数组，桶里有计数就输出对应次数，输出的时候把加的1000减回去，这样就按从大到小输出原来的数啦。

六、总结

桶排序就像我们分类整理东西，把数字按数值放进对应的“桶”里，再按顺序处理桶里的内容。对于0基础的中小学生来说，只要理解数组像小格子、循环像重复做事，就能明白桶排序的基本思路啦。不管是正数排序、去重计数，还是处理负数，都是利用桶（数组）的下标对应数值，计数后再按需求输出的原理。多跟着代码例子跑跑，改改参数，就能更熟练掌握桶排序啦，快去试试吧！