From : blog.mwxu16.cn
简介
从某种程度上讲，桶排序可以说是最快最简单的一种排序算法了，但是缺点也是很明显的，那就是适用范围太小。当待排序的数范围很大时，非常的消耗内存（比如说排序的数的范围是1到1亿，就必须创建1亿个桶（长度为1亿的一维数组，当然这只是假设，并不能创建这么大的数组））。
注意，这里说的是数的范围，而不是实际要排序的数的个数。
例如，第一种情况，只需要排序两个数，1和1000000。第二种情况，需要排序1000000个数，这些数的范围是1到1000000。那么，这两张情况使用桶排序所用的时间和内存是一样的（理想状态下）
算法思想
假如待排序数的范围是0到1000，那么就需要创建一个长度为1001的一维数组，并初始化为0。
然后遍历待排序的数，每出现一次就把该数对应的桶的值加一。
例如出现了一个3，就把编号为3的桶加一。
输出的时候，只需要遍历所有的桶，桶的值是几，就输出几次桶的编号。
如编号为4的桶的值为2，就输出两次4即可。（值为2说明待排序的数中，4出现了两次）
代码实现（JAVA）
package cn.mwxu16.suanfa;
/*
* 桶排序算法
* 算法思想：
* 假如需要排序的数的范围是1-1000，那么就要准备1000个桶（即一个长度为1000的数组）
* 将数组初始化为0
* 每输入一个数，就让该数对应的桶数值加1
* 遍历输出桶，桶的数值是几就输出几次，桶的编号是几就输出几
* 如：编号为2的桶数组为3，即输出3个2
* 优点：速度快
* 缺点：当待排序数范围很大时，太消耗内存。且数不连续时，也浪费资源
*/
public class Tong_sort {
public static void main(String[] args) {
int N = 1001; //定义待排序数的最大范围数加一（不包括该值）
int [] arr ={1,9,44,22,8,456,324,876,523,97,68}; //将待排序的数存入数组中（当然实际操作中也可以直接从键盘输入）
tong_sort(N,arr); //将范围和待排序数传入桶排序方法中
}
public static void tong_sort(int N,int [] arr){
//定义N个桶
int [] book = new int [N];
//初始化桶
for(int i = 0;i<N;i++){
book[i] = 0;
}
//开始桶排序
//遍历待排序数，并把待排序数对应的桶++，
for(int i = 0;i<arr.length ;i++){
book[arr[i]]++; //这里是把待排序数对应的桶的值加一
}
//从小到大输出
//遍历桶，若桶的值x，则输出该桶的编号x次
for(int i=0;i<N;i++){
while(book[i] > 0){
System.out.print(i + ",");
book[i]--;
}
}
}
}
