C++018-C++桶排序及其应用

用户2225445

发布于 2023-10-16 16:56:40

3170

发布于 2023-10-16 16:56:40

文章被收录于专栏：IT从业者张某某

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次而不要多次输出。解决计数问题的时候，我们只需要输出桶中的数据即为元素出现的次数。所以，桶排序其实类似于计数，利用了桶的编号天然有序的性质，过程类似于“唱票”。

模板

#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;
}

题目描述-欢乐的跳

【题目描述】一个

个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了

[1,n-1]

之间的所有整数，则称之符合“欢乐的跳”，如数组

\{1,4,2,3\}

符合“欢乐的跳”，因为差的绝对值分别为：

3,2,1

。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

【输入格式】

每组测试数据第一行以一个整数

n(1 \le n \le 1000)

开始，接下来

个空格隔开的在

[-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 \le n \le 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 提高组] 拼数

【题目描述】设有

个正整数

a_1 \dots a_n

，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。【输入格式】第一行有一个整数，表示数字个数

。第二行有

个整数，表示给出的

个整数

a_i

。【输出格式】一个正整数，表示最大的整数

【样例】1 【样例输入】1

3
13 312 343

【样例输出】1

34331213

【样例】2

【样例输入】2

4
7 13 4 246

【样例输出】2

【提示】

对于全部的测试点，保证

1 \leq n \leq 20

，

1 \leq a_i \leq 10^9

。

#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;
}