0%

桶排序

发表于 分类于

文章字数：333,阅读全文大约需要1分钟

桶排序的时间复杂度为 o(n+k) 即常数

思想

  1. 将有限的桶排列好顺序(包含所有数据或者数据范围)
  2. 将数据挨个放入相应的桶里(如果是范围，就在范围里线性排列)
  3. 按照桶的顺序取出所有数据，此时数据便排好了顺序

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * @param a 需要排序的数组
 * @param max 用于自动生成桶，示例为小范围数字，所以直接生成顺序桶就好了。
 */
 public static void bucketSort(int[] a, int max) {
        int[] buckets;

        if (a == null || max < 1){
            return;
        }

        // 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。
        buckets = new int[max];

        // 1. 计数
        for (int i = 0; i < a.length; i++){
            buckets[a[i]]++;
        }

        // 2. 排序
        for (int i = 0, j = 0; i < max; i++) {
            while ((buckets[i]--) > 0) {
                a[j++] = i;
            }
        }
        buckets = null;
    }