猫史档案馆

大家好，我是新晋No.46少院士祖星，我也打算从今天开始正式启动少院士讲堂，不定期更新，尽请期待~

今天主要是想跟大家聊一聊排序中的桶排序思想，大体上来说桶排序的思想就是将数据放在一个个“桶”，也就是容器中，然后通过在“桶”上贴上标签——也就是给容器进行序号排列来实现数据的储存及查找，这也正是“桶排序”这一名称的由来。

1.首先我们要认识到，大部分的算法其实只是一种思想而不是一种具体的程序语法，其在程序上的体现是由你的目的，也就是你要拿它来干什么决定的，其本身实际上并不具有语法结构，仅仅是一种思想，但为演示方便，我统一采用C++语法结构来描述，如有需其他语言的描述，请在评论区回复，我看到后会补上相应描述的。

2.具体到桶排序，他的储存容器，也就是桶，一般会由数组（Python中可用字典）来充当，当然根据具体使用情况也可采用其他数据储存结构。而桶上的标签一般会由采用的数据储存结构的相应编号充当，例如数组a便以a[i]中的i充当。这个标签的作用是标记桶中的物品，也就是说通过它来判断你桶里装的是什么东西。而容器（“桶”）中的内容并不是要储存的物品，而是这个物品的数量。比如说现在定义一个数组a用来充当容器储存水果，那么我就可以让a[1]储存苹果，也就是用数组编号1来代表苹果，用程序语言来说就是#define 1 apple。然后令a[1]=100.那么就可以看作储存了100个苹果。

3.既然我们现在已经了解了桶排序的思想以及基本使用方法，那具体如何使用呢？别急，比如说现在要统计输入的n个人的成绩并输出优秀人数和及格人数（100分制，90优秀，60及格，n<100）该怎么求呢？

#include<bits/stdc++.h>
using namespace std;
int n,y,g,num,point[100];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>num;
		point[num]++;
	}
	for(int i=0;i<=100;i++)
	{
		cout<<i<<"分的有 "<<point[i]<<"人"<<endl;
		if(i>=60) g+=point[i];
		if(i>=90) y+=point[i];
	}
	cout<<"及格人数为"<<g<<"人"<<endl; 
	cout<<"优秀人数为"<<y<<"人"<<endl; 
}

在这个程序中，point数组是储存数据的容器，n是人数，y是优秀人数，g是及格人数。我们可以运用桶排序的思想，将0~100分每个分数都当成一个桶，然后将得这个分数的人数通过设立临时变量num的方式累加到桶中，这样我们便可以直接在输入阶段完成一个最基本的桶排序。现在每个分数i的人数都以point[i]的形式保存，而接下来只需要按照要求输出即可，在输出时，及格及优秀人数同样可以采用累加的方法，在输出正常分数的同时进行判断，如在及格或优秀线以上则计入累加范围，最后输出总累加和即可。

谢谢阅读，因学业紧张制作匆忙，如有错误烦请指正，鄙人感激不尽，如有任何问题均可在评论区提出，我会在看到的第一时间回答，同时欢迎大家积极评论。