- 创建一定数量的桶(比如用数组、链表作为桶)
- 按照一定的规制(不同类型的数据,规则不同),将序列中的元素均匀分配到对应的桶
- 分别对每个桶进行单独排序
- 将所有非空桶的元素合并成有序序列
- 元素在同种的索引
- 元素值*元素数量
实现
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<>();
buckets[bucketIndex] = bucket;
}
bucket.add(array[i]);
}
int index = 0;
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] == null) continue;
buckets[i].sort(null);
for (Double d : buckets[i]) {
array[index++] = d;
}
}
- 空间复杂度:O(n+m),m是桶的数量
- 时间复杂度:O(n) + mO(n/mlog(n/m)) = O(n+nlog(n/m)) = O(n+nlogn-nlogm)
- 因此为O(n+k),k为nlogn-nlogm
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)