C++018-C++桶排序及其应用
在线练习：
桶排序及其应用
参考：
目标
理解并掌握桶排序基本原理
能够利用桶排序解决常见问题
学会灵活利用桶排序解决复杂问题
桶排序
参考：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
using namespace std;
int n; //要给n个数排序
int bucket[2001]; //满足所有数不超过 bucket[x]的x.-1000 1000 变化为0-2000
#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; }
题目描述-欢乐的跳
【题目描述】
一个 n nn 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 [ 1 , n − 1 ] [1,n-1][1,n−1] 之间的所有整数，则称之符合“欢乐的跳”，如数组 { 1 , 4 , 2 , 3 } \{1,4,2,3\}{1,4,2,3} 符合“欢乐的跳”，因为差的绝对值分别为：3 , 2 , 1 3,2,13,2,1。
给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。
【输入格式】
每组测试数据第一行以一个整数 n ( 1 ≤ n ≤ 1000 ) n(1 \le n \le 1000)n(1≤n≤1000) 开始，接下来 n nn 个空格隔开的在 [ − 1 0 8 , 1 0 8 ] [-10^8,10^8][−10
8
,10
8
] 之间的整数。
【输出格式】
对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。
【样例 #1】
【样例输入 #1】
4 1 4 2 3
【样例输出 #1】
Jolly
【样例 #2】
【样例输入 #2】
5 1 4 2 -1 6
【样例输出 #2】
Not jolly
【 提示】
1 ≤ n ≤ 1000 1 \le n \le 10001≤n≤1000
#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 提高组] 拼数
【 题目描述】
设有 n 个正整数
将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。
【 输入格式】
第一行有一个整数，表示数字个数 n。
第二行有 n nn 个整数，表示给出的 n个整数 
。
【 输出格式】
一个正整数，表示最大的整数
【 样例输入 】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++桶排序序案例，包括相关案例练习。
