在线练习: 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次而不要多次输出。 解决计数问题的时候,我们只需要输出桶中的数据即为元素出现的次数。 所以,桶排序其实类似于计数,利用了桶的编号天然有序的性质,过程类似于“唱票”。
#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
#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
#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
#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
#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】
4 1 4 2 3
【样例输出 #1】
Jolly
【样例 #2】
【样例输入 #2】
5 1 4 2 -1 6
【样例输出 #2】
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;
}
【 题目描述】 设有
个正整数
,将它们联接成一排,相邻数字首尾相接,组成一个最大的整数。 【 输入格式】 第一行有一个整数,表示数字个数
。 第二行有
个整数,表示给出的
个整数
。 【 输出格式】 一个正整数,表示最大的整数
【 样例 】1 【 样例输入 】1
3
13 312 343
【 样例输出 】1
34331213
【 样例 】2
【 样例输入 】2
4
7 13 4 246
【 样例输出 】2
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;
}
本系列为C++学习系列,会介绍C++基础语法,基础算法与数据结构的相关内容。本文为C++桶排序序案例,包括相关案例练习。