今天，我们来讲一种非常高效的排序方法——桶排序！
桶排序的原理
想象一下，我们现在有这样一串数字：1、2、3、4、1、2、3、4、1、2、3、4
我们应该怎么样排序呢？
我们观察一下，首先，这一串数据有很多重复的数字（1~4都出现了3次），那这个特点有什么用呢？别急，我们来排序一下：
1、2、3、4、1、2、3、4
第1个木桶：1
第2个木桶：2
第3个木桶：3
第4个木桶：4
（将数列最开始的4个数扔进木桶里）
1、2、3、4
第1个木桶：1、1
第2个木桶：2、2
第3个木桶：3、3
第4个木桶：4、4
（数列空了）
第1个木桶：1、1、1
第2个木桶：2、2、2
第3个木桶：3、3、3
第4个木桶：4、4、4
那我们已经把所有的数字都装进了木桶里，现在我们要怎么输出？
只要你不算笨的话，应该都会想到怎么输出：首先将第一个木桶里的所有数都输出，将第二个木桶里的数全部输出……
刚刚这种排序方法就叫桶排序，总结一下，桶排序是在数列中的很多数字重复的情况下才能使用的，比如数列1、2、3、4，我们把数列遍历一遍，遇到1，把b[1]++;（b数组用于记录每个数字出现了多少次），遇到2，就把b[2]++;……
注意了，桶排序的时间复杂度是O(n+m)（n是数列的元素个数，m是数列里最大的数字），如果数列里的数字都很小，比如最大的数字只有4，那我们就可以用桶排序，如果有很多的重复数字，我们也可以考虑桶排序
代码：
#includeusing namespace std;long long b[100];//b就是标记数字出现次数用的数组//我这里假设数列中最大的数为99，所以要开100个数组 int main(){long long n;//几个数列元素 cin>>n;//读入 long long a[n+10];for(int i=1;i>a[i];//读入 b[a[i]]++;//那a[i]这一项就可以+1了（找到一个数了） }for(int i=1;i0){//如果b[i]里的数字>0，说明数列里有出现i这个数字 for(int j=1;j<=b[i];j++){//这样才能输出 cout<<i<<" ";//有出现i，就输出i }}}return 0;}