C++018-C++桶排序及其应用-阿里云开发者社区

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号桶，最后依次把桶里的元素倒出来。

设置一个定量的数组当作空桶子。

寻访序列，并且把项目一个一个放到对应的桶子去。

对每个不是空的桶子进行排序。

从不是空的桶子里把项目再放回原来的序列中

桶排序算法中，待排序的数据量和桶的数量并不一定是简单的“一对一”的关系，更多场景中是“多对一”的关系，

3770b0bd5b358c1d141dd152994e0e49_7bbd7719eae04968b81c94b18467234e.png

桶排序应用

我们可以利用桶来完成去重与计数的任务。

解决去重问题时，只需将每个数据装入桶中后，再根据桶中是否有数据( 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;
}

7c24c30022f847f206d3562c810bb69a_46bfefb47336468cbcf77e36f5409045.png

题目描述-模板桶排序

【描述】有n个正整数，数字范围在1~10000之间，请你将这n个数字从小到大输出。n<=100000000。

【输入】输入共2行，第1行是n。第2行是n个整数.

【输出】1行。所有整数从低到高排序后的结果。

【样例输入】

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行。所有整数从高到低排序后的结果。

【样例输入】

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

6899b39f30c70f100fa8a541fad18821_f620e6208cc148b0aab87fc4cc119b04.png

题目描述-年龄排序去重

【描述】小明所在的学校近期统计了师生的年龄数据，教务处主任希望你帮忙把这些年龄按从小到大的顺序排序，重复的年龄只保留一个。作为编程小高手的你能帮他解决这个问题吗?

【输入】输入共2行，第1行是n。第2行是n个整数.

【输出】1行。所有整数去重后从低到高排序后的结果。

【样例输入】

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

5b21872583f8c37359db69148504d32d_55b67fe3f92e428cb0141914ecd87fb1.png

题目描述-统计得分

【描述】北京市中小学刚刚结束期中测试，信息学老师想统计全市学生信息学成绩的得分情况，即某些分数的人数，以便改进教学内容和方法，提高同学们的信息学成绩，同学们写个程序，帮助老师实现吧。【输入】输入共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;
}

ec90b6fc90626fe877e51d753d8a0282_193bbde1eef349bebf0fb437edba535f.png

题目描述-欢乐的跳

【题目描述】

一个 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

,10

] 之间的整数。

【输出格式】

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 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

3e828dc8be23dfda601fee4c3718916d_0b5bb2c6a9bf4744833932d969fc0400.png

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

805d2e8bf83b5de58dd84c6fd22f723d_33d9e999ab3d4cf3a97cbf784b8838f9.png

题目描述-[NOIP1998 提高组] 拼数

【题目描述】

设有 n 个正整数将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

【输入格式】

第一行有一个整数，表示数字个数 n。

第二行有 n nn 个整数，表示给出的 n个整数。

【输出格式】

一个正整数，表示最大的整数

【样例输入】1

3
13 312 343

【样例输出】1

34331213

【样例】2

【样例输入】2

4
7 13 4 246

【样例输出】2

【提示】

对于全部的测试点，保证

a5ff2f73a3cc19ae7c260361214b3237_1093ccc2a03c420a8a288086012c63a7.png

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

24c29951a8e6cfc39263b6e6c1e72993_f2ef83f50f2f4ce1a61c5d529192c881.png

作业

56d3dcb033896fce5d443544b7d1462f_532054e06586474eb7f8545e1470953c.png

在线练习：

http://noi.openjudge.cn/

总结

本系列为C++学习系列，会介绍C++基础语法，基础算法与数据结构的相关内容。本文为C++桶排序序案例，包括相关案例练习。

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