算法 - 桶排序（Bucket Sort）

本文主要是介绍算法 - 桶排序（Bucket Sort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 执行流程：

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

• 元素在同种的索引
• 元素值*元素数量
  

实现

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

这篇关于算法 - 桶排序（Bucket Sort）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---