高级天翼
我对桶的知识点有亿点不懂，求班课上过的同学发些讲义
高级光能
桶计数课后讲义（火箭v2）
桶计数
引言
假设有一堆标了号码的球散落一地，需要我们统计标号1的球有多少个？标号2的球有多少个？标号3的球有多少个？……
如果我们对球不做整理，直接去数，可能眼睛数花了还没数对。
此时我们准备好若干个桶：1号桶，2号桶，3号桶，…… 将每种标号的球投入对应的桶中，这样每个桶中球的个数就比较清楚了。
一．定义桶数组
1. 桶数组要定义在主函数外，或者定义时将数组元素值初始化为0。
因为我们要用数组元素来计数，每个数组元素的初值都要确保是0。
2. 桶数组的大小要根据要计数的数据的最大值来确定。
因为桶数组的下标对应要计数的数据，要保证桶数组计数时下标不越界。
二．桶数组计数的过程
对于某数组中的数，我们想要统计不同的数有分别有多少个。
则我们可以定义一个桶数组b[10]； （桶数组要保证最大下标不小于5）
一开始桶数组中所有元素的值都是0，然后我们遍历a数组，开始计数：
遍历a数组：1，2，3，2，3，5，1，5，2，3
遇到1，b[1]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
遇到5，b[5]++ ;
遇到1，b[1]++ ;
遇到5，b[5]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
所以最后b[1]=2，b[2]=3，b[3]=3，b[4]=0，b[5]=2。
表示原来的数组中 1有2个，2有3个，3有3个，4没有，5有2个。
三．本节知识点脉络
桶计数
高级天翼
急，becourse我要写作业
高级启示者
高级光能
桶排序课后讲义（火箭v2）
桶排序
一、桶排序的原理
利用桶数组记录序列中每个数字出现的次数。由于用桶数组的下标对应序列中的数字，所以只要按下标从小到大的顺序，将桶数组记录的数字输出即可（注意桶数组的下标是对应数字，而桶元素的值对应该数字出现的次数）
二、桶排序的过程
如果需要排序的数据在一个明显有限范围内（整型）时，我们可以用数组下标与数值一一对应，将每个数值放进与它对应的数组元素（桶）中，然后按照顺序输出各桶的值，将得到有序的序列。
比如：对于序列
从小到大排序：
定义一个桶（即数组）数组a[10]
桶数组a的所有元素赋初值为0，然后将每个数字计入对应桶元素中，
最后，按照从小到大的顺序遍历桶数组，如果桶元素a[i]的值非0，说明该元素下标对应的数字出现过，并且a[i]的值就是i这个数的个数，即要输出a[i]个i。
代码实现
如果要输入n个不超过1000的数字，使用桶排序从小到大输出，代码如下：
int a[1001]; //每个数的范围在1~1000 ，所以定义a[1001] （1~1000的桶） int main(){ int n ,t; cin>>n; for(int i=1;i<=n;i++){ //输入n个数 cin>>t; a[t]++; //用桶的下标存这个数，桶的值++ } for(int i=1;i<=1000;i++){ //遍历桶数组 for(int j=1;j<=a[i];j++){ //输出a[i]个i（a[i]为0则不输出） cout<<i<<' '; } } return 0; }
三．本节知识点脉络
桶排序
高级光能
桶去重+桶的练习课后讲义（火箭v2）
桶去重+桶的练习
一．桶去重的原理
利用桶数组对输入的数据进行统计，如果某数字出现过，那么以该数字作下标的桶数组元素值必然大于0，因此我们可以知道在一个范围内那些数字出现，哪些数字没出现过。
而对于出现过的数字，不管它出现了几次，输出时都只输出一遍，即完成了去重的功能。
二．桶去重的过程
对于某数组中的数，先利用桶数组记录某个数的个数。
定义b数组记录a数组中每个数字出现的次数：
如果要求按照原数组中的顺序输出所有数字（重复的只输出一次）
则需要遍历a数组，对每个数字做判断，是否对应的桶元素值大于0，如果大于0，则输出这个元素，但同时要把桶元素清零，防止后面输出同样的数字（去重）。
对上述数组来说，有如下过程：
遍历a数组，
遇到1，判断b[1]是大于0的，输出1，并将b[1]=0;
遇到2，判断b[2]是大于0的，输出2，并将b[2]=0;
遇到3，判断b[3]是大于0的，输出3，并将b[3]=0;
遇到2，判断b[2]是0，不输出;
遇到3，判断b[3]是0，不输出;
遇到5，判断b[5]是大于0的，输出5，并将b[5]=0;
遇到1，判断b[1]是0，不输出;
遇到5，判断b[5]是0，不输出;
遇到2，判断b[2]是0，不输出;
遇到3，判断b[3]是0，不输出;
所以最终输出的结果是1,2,3,5。
三、非正整数数据使用桶排序时的处理办法
将数据先转化为正整数！
如输入一组负数，先将负数统一加上一个固定值变成正整数，接着进行桶排序，输出时再将元素减去固定值后输出。
如输入一组小数，先将小数乘以一个固定值（10或100或1000……）使得这些数变成正整数，接着就可以进行桶排序，输出时再将元素除以固定值还原。
三．本节知识点脉络
桶去重+桶的练习
新手启示者
桶计数
引言
假设有一堆标了号码的球散落一地，需要我们统计标号1的球有多少个？标号2的球有多少个？标号3的球有多少个？……
如果我们对球不做整理，直接去数，可能眼睛数花了还没数对。
此时我们准备好若干个桶：1号桶，2号桶，3号桶，…… 将每种标号的球投入对应的桶中，这样每个桶中球的个数就比较清楚了。
一．定义桶数组
1. 桶数组要定义在主函数外，或者定义时将数组元素值初始化为0。
因为我们要用数组元素来计数，每个数组元素的初值都要确保是0。
2. 桶数组的大小要根据要计数的数据的最大值来确定。
因为桶数组的下标对应要计数的数据，要保证桶数组计数时下标不越界。
二．桶数组计数的过程
对于某数组中的数，我们想要统计不同的数有分别有多少个。
则我们可以定义一个桶数组b[10]； （桶数组要保证最大下标不小于5）
一开始桶数组中所有元素的值都是0，然后我们遍历a数组，开始计数：
遍历a数组：1，2，3，2，3，5，1，5，2，3
遇到1，b[1]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
遇到5，b[5]++ ;
遇到1，b[1]++ ;
遇到5，b[5]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
所以最后b[1]=2，b[2]=3，b[3]=3，b[4]=0，b[5]=2。
表示原来的数组中 1有2个，2有3个，3有3个，4没有，5有2个。
三．本节知识点脉络
新手启示者
桶排序
一、桶排序的原理
利用桶数组记录序列中每个数字出现的次数。由于用桶数组的下标对应序列中的数字，所以只要按下标从小到大的顺序，将桶数组记录的数字输出即可（注意桶数组的下标是对应数字，而桶元素的值对应该数字出现的次数）
二、桶排序的过程
如果需要排序的数据在一个明显有限范围内（整型）时，我们可以用数组下标与数值一一对应，将每个数值放进与它对应的数组元素（桶）中，然后按照顺序输出各桶的值，将得到有序的序列。
比如：对于序列
从小到大排序：
定义一个桶（即数组）数组a[10]
桶数组a的所有元素赋初值为0，然后将每个数字计入对应桶元素中，
最后，按照从小到大的顺序遍历桶数组，如果桶元素a[i]的值非0，说明该元素下标对应的数字出现过，并且a[i]的值就是i这个数的个数，即要输出a[i]个i。
代码实现
如果要输入n个不超过1000的数字，使用桶排序从小到大输出，代码如下：
int a[1001]; //每个数的范围在1~1000 ，所以定义a[1001] （1~1000的桶） int main(){ int n ,t; cin>>n; for(int i=1;i<=n;i++){ //输入n个数 cin>>t; a[t]++; //用桶的下标存这个数，桶的值++ } for(int i=1;i<=1000;i++){ //遍历桶数组 for(int j=1;j<=a[i];j++){ //输出a[i]个i（a[i]为0则不输出） cout<<i<<' '; } } return 0; }
三．本节知识点脉络
新手启示者
桶去重+桶的练习
一．桶去重的原理
利用桶数组对输入的数据进行统计，如果某数字出现过，那么以该数字作下标的桶数组元素值必然大于0，因此我们可以知道在一个范围内那些数字出现，哪些数字没出现过。
而对于出现过的数字，不管它出现了几次，输出时都只输出一遍，即完成了去重的功能。
二．桶去重的过程
对于某数组中的数，先利用桶数组记录某个数的个数。
定义b数组记录a数组中每个数字出现的次数：
如果要求按照原数组中的顺序输出所有数字（重复的只输出一次）
则需要遍历a数组，对每个数字做判断，是否对应的桶元素值大于0，如果大于0，则输出这个元素，但同时要把桶元素清零，防止后面输出同样的数字（去重）。
对上述数组来说，有如下过程：
遍历a数组，
遇到1，判断b[1]是大于0的，输出1，并将b[1]=0;
遇到2，判断b[2]是大于0的，输出2，并将b[2]=0;
遇到3，判断b[3]是大于0的，输出3，并将b[3]=0;
遇到2，判断b[2]是0，不输出;
遇到3，判断b[3]是0，不输出;
遇到5，判断b[5]是大于0的，输出5，并将b[5]=0;
遇到1，判断b[1]是0，不输出;
遇到5，判断b[5]是0，不输出;
遇到2，判断b[2]是0，不输出;
遇到3，判断b[3]是0，不输出;
所以最终输出的结果是1,2,3,5。
三、非正整数数据使用桶排序时的处理办法
将数据先转化为正整数！
如输入一组负数，先将负数统一加上一个固定值变成正整数，接着进行桶排序，输出时再将元素减去固定值后输出。
如输入一组小数，先将小数乘以一个固定值（10或100或1000……）使得这些数变成正整数，接着就可以进行桶排序，输出时再将元素除以固定值还原。
三．本节知识点脉络
