C 018-C 桶排序及其应用
在线练习： http://noi.openjudge.cn/ https://www.luogu.com.cn/
桶排序及其应用
参考：
目标
理解并掌握桶排序基本原理 能够利用桶排序解决常见问题 学会灵活利用桶排序解决复杂问题
桶排序
参考：https://blog.csdn.net/m0_64036070/article/details/123826962 https://blog.csdn.net/Passerby_XX/article/details/123147928 桶排序是计数排序的升级版，也是分治算法。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。简言之，将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
设置一个定量的数组当作空桶子。 寻访序列，并且把项目一个一个放到对应的桶子去。 对每个不是空的桶子进行排序。 从不是空的桶子里把项目再放回原来的序列中
桶排序算法中，待排序的数据量和桶的数量并不一定是简单的“一对一”的关系，更多场景中是“多对一”的关系，
桶排序应用
我们可以利用桶来完成
去重与计数的任务。 解决去重问题时，只需将每个数据装入桶中后，再根据桶中是否有数据( tong[i]>0),来输出对应的桶的编号,只输出1次而不要多次输出。 解决计数问题的时候，我们只需要输出桶中的数据即为元素出现的次数。 所以，桶排序其实类似于计数，利用了桶的编号天然有序的性质，过程类似于“唱票”。
模板
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n; //要给n个数排序
int bucket[1005]; //满足所有数不超过 bucket[x]的x
int main()
{
cin>>n;
for(int i=1;i<=n;i )
{
int a;
cin>>a;
bucket[a] ; //进入相应的区域（桶）
//如果题目要求把重复的数删掉（去重）
//可以写 bucket[a]=1;
}
for(int i=0;i<=1005;i ) //要把所有区域里的数“拽”出来
while(bucket[i]>0)
{
cout<<i<<' '; //i指的是数
bucket[i]--; //bucket[i]指的是区域 i里剩余数的数量
}
return 0;
}
题目描述-模板桶排序
【描述】有n个正整数，数字范围在1~10000之间，请你将这n个数字从小到大输出。n<=100000000。 【输入】输入共2行，第1行是n。第2行是n个整数. 【输出】1行。所有整数从低到高排序后的结果。 【样例输入】 10 1 2 3 4 6 5 9 8 7 0 【输出】 0 1 2 3 4 5 6 7 8 9
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n; //要给n个数排序
int bucket[10005]; //满足所有数不超过 bucket[x]的x
int main()
{
cin>>n;
for(int i=1;i<=n;i )
{
int a;
cin>>a;
bucket[a] ; //进入相应的区域（桶）
//如果题目要求把重复的数删掉（去重）
//可以写 bucket[a]=1;
}
for(int i=0;i<=10000;i ) //要把所有区域里的数“拽”出来
// while(bucket[i]>0)
// {
// cout<<i<<' '; //i指的是数
// bucket[i]--; //bucket[i]指的是区域 i里剩余数的数量
// }
for(int j=1;j<=bucket[i];j )
{
cout<<i<<" ";
}
return 0;
}题目描述-带负数桶排序
【描述】有n个正整数，数字范围在-1000~1000之间，请你将这n个数字从小到大输出。n<=100000000。 【输入】输入共2行，第1行是n。第2行是n个整数. 【输出】1行。所有整数从高到低排序后的结果。 【样例输入】 6 11 22 33 -44 -32 1 【输出】 33 22 11 1 -32 -44
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n; //要给n个数排序
int bucket[2001]; //满足所有数不超过 bucket[x]的x.-1000 1000 变化为0-2000
int main()
{
cin>>n;
for(int i=1;i<=n;i )
{
int a;
cin>>a;
bucket[a 1000] ; //进入相应的区域（桶）
//如果题目要求把重复的数删掉（去重）
//可以写 bucket[a]=1;
}
for(int i=2000;i>=0;i--) //要把所有区域里的数“拽”出来
for(int j=1;j<=bucket[i];j )
{
cout<<i-1000<<" "; //减去1000
}
return 0;
}
题目描述-年龄排序去重
【描述】小明所在的学校近期统计了师生的年龄数据，教务处主任希望你帮忙把这些年龄按从小到大的顺序排序，重复的年龄只保留一个。作为编程小高手的你能帮他解决这个问题吗? 【输入】输入共2行，第1行是n。第2行是n个整数. 【输出】1行。所有整数去重后从低到高排序后的结果。 【样例输入】 6 11 12 12 10 11 13 【输出】 10 11 12 13
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n; //要给n个数排序
int bucket[105]; //满足所有数不超过 bucket[x]的x.-1000 1000 变化为0-2000
int main()
{
cin>>n;
for(int i=1;i<=n;i )
{
int a;
cin>>a;
bucket[a] ; //进入相应的区域（桶）
//如果题目要求把重复的数删掉（去重）
//可以写 bucket[a]=1;
}
for(int i=1;i<=100;i ) //要把所有区域里的数“拽”出来
if(bucket[i]) cout<<i<<" ";
return 0;
}
题目描述-统计得分
【描述】北京市中小学刚刚结束期中测试，信息学老师想统计全市学生信息学成绩的得分情况，即某些分数的人数，以便改进教学内容和方法，提高同学们的信息学成绩，同学们写个程序，帮助老师实现吧。【输入】输入共3行，第1行是n和k。第2行是n个整数，第3行是k个得分; 【输出】1行k个整数，分别为k个得分的人数; 【样例输入】 6 2 11 12 12 10 11 13 12 13 【输出】 2 1
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n,k,score; //要给n个数排序
int bucket[105]; //满足所有数不超过 bucket[x]的x.-1000 1000 变化为0-2000
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i )
{
int a;
cin>>a;
bucket[a] ; //进入相应的区域（桶）
//如果题目要求把重复的数删掉（去重）
//可以写 bucket[a]=1;
}
for(int i=1;i<=k;i )
{
cin>>score;
cout<<bucket[score]<<" ";
}
return 0;
}
题目描述-欢乐的跳
【题目描述】 一个
个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了
之间的所有整数，则称之符合“欢乐的跳”，如数组
符合“欢乐的跳”，因为差的绝对值分别为：
。
给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。
【输入格式】
每组测试数据第一行以一个整数
开始，接下来
个空格隔开的在
之间的整数。
【输出格式】
对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。
【样例 #1】
【样例输入 #1】
代码语言：javascript复制4 1 4 2 3【样例输出 #1】
代码语言：javascript复制Jolly【样例 #2】
【样例输入 #2】
代码语言：javascript复制5 1 4 2 -1 6【样例输出 #2】
代码语言：javascript复制Not jolly【 提示】
#include <bits/stdc .h>
using namespace std;
int main()
{
int a[1100],b[1100],n;
cin>>n;
for(int i=1;i<=n;i )
{
cin>>a[i];
}
for(int j=1;j<=n-1;j )
{
b[j]=abs(a[j]-a[j 1]);
}
sort(b 1,b 1 n-1);
int s =0;
for(int k=1;k<=n-1;k )
{
if(b[k]==k)s ;
}
if(s==n-1)cout<<"Jolly";
else cout<<"Not jolly";
return 0;
}
题目描述-[NOIP1998 提高组] 拼数
【 题目描述】 设有
个正整数
，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。 【 输入格式】 第一行有一个整数，表示数字个数
。 第二行有
个整数，表示给出的
个整数
。 【 输出格式】 一个正整数，表示最大的整数
【 样例 】1 【 样例输入 】1
代码语言：javascript复制3
13 312 343【 样例输出 】1
代码语言：javascript复制34331213【 样例 】2
【 样例输入 】2
代码语言：javascript复制4
7 13 4 246【 样例输出 】2
代码语言：javascript复制7424613【 提示】
对于全部的测试点，保证
，
。
#include <bits/stdc .h>
using namespace std;
bool cmp(string a,string b){
return a b>b a;
}
int main()
{
string a[22];
int n;
cin>>n;
for(int i=1;i<=n;i ) cin>>a[i];
sort(a 1,a 1 n.cmp);
for(int i=1;i<=n;i ) cout<<a[i];
return 0;
}#include <bits/stdc .h>
using namespace std;
bool cmp(string a,string b){
return a b>b a;
}
int main()
{
string a[22],key;
int n,j;
cin>>n;
for(int i=1;i<=n;i ) cin>>a[i];
for(int i=2;i<=n;i )
{
key =a[i];
for(j=i-1;j>=1;j--)
{
if(key a[j]>a[j] key) a[j 1]=a[j];//key要插入到a[j]前
else break;
}
a[j 1]=key;
}
for(int i=1;i<=n;i ) cout<<a[i];
return 0;
}
作业
在线练习：
http://noi.openjudge.cn/
总结
本系列为C 学习系列，会介绍C 基础语法，基础算法与数据结构的相关内容。本文为C 桶排序序案例，包括相关案例练习。
