关于桶排序的文章，我几乎是没有见过。见过也看不懂，所以只好学会以后自己写一个了。
桶排序特点：
- 桶排序是稳定的
- 桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
- 桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法
桶排序与其他排序的比较：
基数排序，与选择，冒泡，插入排序不同的是，前者都属于【比较性】排序，而基数排序是【分配式】排序，所以他又称”桶排“；
桶排，顾名思义，就是透过数据的部分资讯，将待排序的元素分配至某些【桶】中，从而达到排序的作用，他属于稳定性的排序。
下面举例子来讲吧：Codevs1487 大批整数排序
【题目描述】
CodeVS开发者有话说：
codevs自从换了评测机，新评测机的内存计算机制发生变化
计算内存的时候会包括栈空间 swap空间
这题的2M是单指内存空间。。。十分抱歉！
现在有一大批（总数不超过10000000个）1到10之间的整数，现在请你从小到大进行排序输出。
（测试数据将超过11MB。）
输入描述 Input Description
第一行表示将下排序的个数N；
第2行到最后一行，每行一个数，表示有待排序的数（均是1-10之间的数，含1和10）
（注：最后有一空行）
输出描述 Output Description
输出N个从小到大排列好的数，每行一个（注：最后有一空行）
样例输入 Sample Input
11
9
10
1
2
3
4
5
6
7
8
9
样例输出 Sample Output
1
2
3
4
5
6
7
8
9
9
10
分析：根据题目不难想起解题方法。肯定是排序之后又是什么排序。我最先想到的是STL的sort。之后试了一下。
第二个数据点没有过。之后我重新审了一下题目【现在有一大批（总数不超过10000000个）1到10之间的整数】很明显。SORT承受不了这么多组数。受不了受不了受不了，这日子没发过了啊。怎么办……
之后呢，聪明的古人发明了快速简洁的排序——桶排序（没找到发明人和日期。）
对此题目有了其他解法。（桶排序似乎出现早
#include <cstdio>
#include <iostream>
using namespace std;
int n,a[11],x;
int main()
{
menset（a，0，sizeof（a））；
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[x]++;
}
for(int i=1;i<=10;i++)
if(a[i]!=0)
{
for(int j=1;j<=a[i];j++)
printf("%d\n",i);
}
return 0;
}
首先n为输出N个从小到大排列好的数。之后就进入了核心代码。【1到10之间的整数】这一个条件，就可以得到需要10个【桶】就OK。在学数组的时候学过，需要把数组开大一点。【桶】也要大一点。就开十一个。下面就考虑桶的表示。等等==刚刚说了什么数组？
嗯？数组=桶。
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[x]++;
}
就将其分为11个桶（一个桶备用）。X为1~10的数。也为每输入一个数就判断在哪一个桶里并放入。桶内数量+1.这段代码应该不难理解。看下一段。
for(int i=1;i<=10;i++)
if(a[i]!=0)
{
for(int j=1;j<=a[i];j++)
printf("%d\n",i);
}
判断并输出。首先遍历10个桶。之后判断桶内数量是否为0.如果0下一个，如果不是0，是几就输出几。
好哒，桶排就这么简单，下次再见！
支付宝扫一扫
