桶排序（Bucket Sort）是一种基于分布的排序算法，它将元素分散到几个桶中，然后对每个桶分别排序，最后合并所有桶中的元素。桶排序适用于均匀分布的输入，能够在平均情况下达到线性时间复杂度。
桶排序实现
示例代码1：基本桶排序
import java.util.ArrayList; import java.util.Collections; public class BucketSort { public static void bucketSort(float[] arr, int numBuckets) { if (arr.length <= 1) return; // 创建桶 ArrayList<Float>[] buckets = new ArrayList[numBuckets]; for (int i = 0; i < numBuckets; i++) { buckets[i] = new ArrayList<>(); } // 将元素分配到桶中 for (float num : arr) { int bucketIndex = (int) (num * numBuckets); // 假设元素范围在[0, 1)之间 buckets[bucketIndex].add(num); } // 对每个桶进行排序 for (ArrayList<Float> bucket : buckets) { Collections.sort(bucket); } // 合并所有桶中的元素 int index = 0; for (ArrayList<Float> bucket : buckets) { for (float num : bucket) { arr[index++] = num; } } } public static void main(String[] args) { float[] arr = {0.42f, 0.32f, 0.23f, 0.52f, 0.25f, 0.47f, 0.51f}; System.out.println("排序前:"); for (float num : arr) { System.out.print(num + " "); } bucketSort(arr, 5); System.out.println("\n排序后:"); for (float num : arr) { System.out.print(num + " "); } } }
代码注释
创建桶：根据输入数组的长度和预定义的桶数量，初始化一个桶数组，每个桶都是一个 ArrayList。
分配元素：将每个元素分配到相应的桶中，这里假设输入元素范围在 [0, 1) 之间，因此可以直接使用 num * numBuckets 计算桶的索引。
排序桶：使用 Collections.sort 对每个桶进行排序。
合并桶：将所有桶中的元素按顺序合并到原数组中。
示例代码2：支持更大范围的桶排序
下面的示例支持任意范围的浮点数输入，并且桶的数量动态计算。
import java.util.ArrayList; import java.util.Collections; public class BucketSort { public static void bucketSort(float[] arr) { if (arr.length <= 1) return; // 找到数组中的最大值和最小值 float max = arr[0]; float min = arr[0]; for (float num : arr) { if (num > max) max = num; if (num < min) min = num; } // 初始化桶 int numBuckets = (int) Math.sqrt(arr.length); // 桶的数量可以根据需求调整 ArrayList<Float>[] buckets = new ArrayList[numBuckets]; for (int i = 0; i < numBuckets; i++) { buckets[i] = new ArrayList<>(); } // 将元素分配到桶中 float range = max - min; for (float num : arr) { int bucketIndex = (int) ((num - min) / range * (numBuckets - 1)); buckets[bucketIndex].add(num); } // 对每个桶进行排序 for (ArrayList<Float> bucket : buckets) { Collections.sort(bucket); } // 合并所有桶中的元素 int index = 0; for (ArrayList<Float> bucket : buckets) { for (float num : bucket) { arr[index++] = num; } } } public static void main(String[] args) { float[] arr = {4.2f, 3.2f, 2.3f, 5.2f, 2.5f, 4.7f, 5.1f}; System.out.println("排序前:"); for (float num : arr) { System.out.print(num + " "); } bucketSort(arr); System.out.println("\n排序后:"); for (float num : arr) { System.out.print(num + " "); } } }
代码注释
找到最大值和最小值：遍历数组，找到最大值和最小值，以便后续计算每个元素的桶索引。
初始化桶：根据数组长度的平方根初始化桶的数量，每个桶都是一个 ArrayList。
分配元素：根据元素值和最小值、范围以及桶数量计算桶索引，将元素分配到相应的桶中。
排序桶：使用 Collections.sort 对每个桶进行排序。
合并桶：将所有桶中的元素按顺序合并到原数组中。
