原理

  1. 事先准备N个桶，每个桶代表从1到N的值。
  2. 将N-1个待排序数字，按照N桶的数字进行放入。
  3. 相同的桶放入了n次相同数字，则相应的桶的值为n。
  4. 遍历N个桶，只要桶中的值大于0，则输出序号，值为2，则输出两次该序号。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 *  桶排序
 */
public static void sort(int[] array, int range) {
    
    // 桶
    int[] bucket = new int[range];
    // 遍历array，向bucket中表示
    for (int i = 0; i < array.length; i++) {
        int index = array[i];
        bucket[index] = bucket[index] + 1;
    }
    
    // 输出
    for (int i = 0; i < bucket.length; i++) {
        for (int j = 0; j < bucket[i]; j++) {
            System.out.println(i);
        }
    }
}

结论

桶排序实际上只需要遍历一遍所有的元素，然后依次放入制定的位置。如果加上输出排序的时间，那么时间复杂度为O(n+m)，n：待排序的元素个数，m：桶的个数。很快，但是空间消耗比较大。

元素跨度越大，空间消耗越大，空间利用率越低，浪费越大。

但是 快 ！

适用场景

数据分布相对均匀，跨度不太大的场景。

改进

利用类似散列表的方式，改善空间利用率。