介绍
桶排序是一种时间复杂度为O（M+N）的一种排序，不好的地方在于浪费空间。
特点是利用了数组的索引。
桶的个数是排序的最大数+1。
打个案例：要对一堆数据进行时间复杂度为O（M+N）的排序就可以使用这个算法，缺点：打个比方，有10个要排序的数，其中最大数是1000，那么你申请的桶就需要1001。
案例
这个算法就好比有11个桶，编号从0~10。每出现一个数，就将对应编号的桶中的放一个小旗子，最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子，表示2出现了一次；3号桶中有1个小旗子，表示3出现了一次；5号桶中有2个小旗子，表示5出现了两次；8号桶中有1个小旗子，表示8出现了一次。
注意：如果需要对数据范围在0~1000之间的整数进行排序，我们需要1001个桶。
代码
public static void main(String[] args) {
//生成数据源
//待排序数
int n=5;
int[] src=new int[n];
src[0]=5;
src[1]=3;
src[2]=5;
src[3]=2;
src[4]=8;
//桶个数
int m=11;
//定义桶
int[] book=new int[m];
//将数字放到桶里面
for (int i=0; i<n;i++) {
book[src[i]]++;
}
//打印排序
for (int i=0; i<m;i++) {
for(int j=1;j<=book[i];j++) //出现了几次就将桶的编号打印几次
System.out.println(i);
}
}
// 结果
// 2
// 3
// 5
// 5
// 8
时间复杂度
最后来说下时间复杂度的问题。
代码第一次for循环n次 （n为待排序数的个数），代码第二次for循环m次 （m为桶的个数），该算法的时间复杂度是O(m+n)，
我们在说时间复杂度时候可以忽略较小的常数，最终桶排序的时间复杂度为O(M+N)。
| 
转播
