桶排序

流程

• 创建一定数量的桶，例如 数组、链表
• 按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶
• 分别对每个桶进行单独排序
• 将所有非空桶的元素合并成有序序列

元素在桶中的索引

• 以 float 为例： 索引 = 元素 * 元素数目

伪代码

桶数组

double[] array = {0.34, 0.47, 0.29, 0.84, 0.45, 0.38, 0.35, 0.76};

// 桶数组

List<Double>[] buckets = new List[array.length];

for (int i = 0; i < array.length; i++) {

int bucketIndex = (int) (array[i] * array.length);

List<Double> bucket = buckets[bucketIndex];

if (bucket == null) {

bucket = new LinkedList<>();

beckets[bucketIndex] = bucket;

}

bucket.add(array[i]);

}

对每个桶进行排序

int index = 0;

for (int i = 0; i < bucket.length; i++) {

if (buckets[i] == null) continue;

buckets[i].sort(null); // original Java API

for (Double b : buckets[i]) {

array[index++] = d;

}

}

复杂度

• 空间复杂度 O(n + m) ， m 是桶的数目
• 时间复杂度： 认为每个桶里都存放着 n/m 个元素，单个桶中排序算法的时间复杂度为 nlogn，则单个桶的排序时间复杂度为 n/m log(n/m)，最终 `O(n + nlogn - n*logm )，简记为 O(n + k)`