最快最简单的排序——桶排序

桶排序

---

前言

这两页是从啊哈算法这本书拍的，说的很明确，桶排序就是有一些可以承载一个或多个元素的桶，将这些元素对号入座放在指定的桶里，然后遍历这些桶。可能这么说不是很好理解，看一段代码

#include
int main()
{
int a[10],i,j,t;//创建10个桶 
for(i=0;i<=10;i++)
a[i]=0;//初始化每个桶都为0 
for(i=1;i<=5;i++)
	{
		scanf("%d",&t);//给t赋值 
		a[t]++;//对桶计数 
	} 
	for(i=0;i<=10;i++)//依次判断所有的桶 
	{
	for(j=1;j<=a[i];j++)
	printf("%d ",i);//出现几次就打印几次 
	}
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

可以发现的确进行了从小到大排序，如何从大到小排序呢，把判断的从大到小写就行，for(i=10;i>=0;i–)
在看下面一段代码

#include
int main()
{
int a[1001],i,j,t,n;
for(i=0;i<=1000;i++)

a[i]=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
	{
		scanf("%d",&t);
		a[t]++;
	} 
	for(i=1000;i>=0;i--)
	{
	for(j=1;j<=a[i];j++)
	printf("%d ",i);
	}
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

虽然可以排序，但是它非常浪费空间，比如你要排序5个数范围是100000，那么你也要100000个桶。很明显，这个非常浪费空间。
再来看如果我们要把得分和姓名都排序出来呢，桶排序就不可以了，这个时候应该用什么呢？