Java 桶排序算法
最后修改时间：2025 年 4 月 16 日
排序算法简介
算法是解决问题或执行计算的逐步过程。排序算法按特定顺序排列元素，通常是数值或词典顺序。高效的排序对于优化其他算法至关重要。
常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和桶排序。每种算法都有不同的时间和空间复杂度特征。
桶排序概述
桶排序是一种分配排序算法，通过将元素分配到多个桶中来工作。然后，对每个桶单独排序，可以使用不同的算法或递归地应用桶排序。
当输入在范围内均匀分布时，桶排序效率很高。它的平均情况时间复杂度为 O(n + k)，其中 n 是元素数量，k 是桶的数量。
数字的桶排序实现
这是一个用 Java 实现的数字数据桶排序的基本示例。此示例按升序对整数数组进行排序。
BucketSortNumbers.java
package com.zetcode;
import java.util.ArrayList;
import java.util.Collections;
public class BucketSortNumbers {
public static void bucketSort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return;
}
// Find minimum and maximum values
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// Initialize buckets
int bucketCount = (maxValue - minValue) / bucketSize + 1;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<Integer>());
}
// Distribute input array values into buckets
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (arr[i] - minValue) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
// Sort buckets and place back into input array
int currentIndex = 0;
for (int i = 0; i < buckets.size(); i++) {
ArrayList<Integer> bucket = buckets.get(i);
Collections.sort(bucket);
for (int j = 0; j < bucket.size(); j++) {
arr[currentIndex++] = bucket.get(j);
}
}
}
public static void main(String[] args) {
int[] data = {29, 25, 3, 49, 9, 37, 21, 43};
System.out.println("Before sorting:");
for (int num : data) {
System.out.print(num + " ");
}
bucketSort(data, 10);
System.out.println("\nAfter sorting (ascending):");
for (int num : data) {
System.out.print(num + " ");
}
}
}
此实现首先找到值的范围，创建适当的桶，将元素分配到这些桶中，对每个桶进行排序，最后将它们连接起来。bucketSize 参数控制使用的桶的数量。
降序排序
要按降序排序，我们可以反转排序后的桶，或者修改集合排序以使用反向比较器。这是一个修改后的版本。
BucketSortDescending.java
package com.zetcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class BucketSortDescending {
public static void bucketSort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
int bucketCount = (maxValue - minValue) / bucketSize + 1;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<Integer>());
}
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (arr[i] - minValue) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
int currentIndex = 0;
for (int i = buckets.size() - 1; i >= 0; i--) {
ArrayList<Integer> bucket = buckets.get(i);
Collections.sort(bucket, Comparator.reverseOrder());
for (int j = 0; j < bucket.size(); j++) {
arr[currentIndex++] = bucket.get(j);
}
}
}
public static void main(String[] args) {
int[] data = {29, 25, 3, 49, 9, 37, 21, 43};
System.out.println("Before sorting:");
for (int num : data) {
System.out.print(num + " ");
}
bucketSort(data, 10);
System.out.println("\nAfter sorting (descending):");
for (int num : data) {
System.out.print(num + " ");
}
}
}
关键更改是使用 Comparator.reverseOrder 对桶进行排序，并以相反的顺序迭代桶。这会生成一个降序排序的数组。
字符串的桶排序
桶排序也可以应用于字符串，方法是使用它们的字符作为键。这是一个基于字符串的第一个字符对字符串进行排序的实现。
BucketSortStrings.java
package com.zetcode;
import java.util.ArrayList;
import java.util.Collections;
public class BucketSortStrings {
public static void bucketSort(String[] arr) {
if (arr.length == 0) {
return;
}
// Determine range (ASCII values of first characters)
int minValue = (int) arr[0].charAt(0);
int maxValue = (int) arr[0].charAt(0);
for (int i = 1; i < arr.length; i++) {
int firstChar = (int) arr[i].charAt(0);
if (firstChar < minValue) {
minValue = firstChar;
} else if (firstChar > maxValue) {
maxValue = firstChar;
}
}
// Initialize buckets
int bucketCount = maxValue - minValue + 1;
ArrayList<ArrayList<String>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<String>());
}
// Distribute strings into buckets based on first character
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (int) arr[i].charAt(0) - minValue;
buckets.get(bucketIndex).add(arr[i]);
}
// Sort each bucket and concatenate
int currentIndex = 0;
for (int i = 0; i < buckets.size(); i++) {
ArrayList<String> bucket = buckets.get(i);
Collections.sort(bucket);
for (int j = 0; j < bucket.size(); j++) {
arr[currentIndex++] = bucket.get(j);
}
}
}
public static void main(String[] args) {
String[] words = {"apple", "banana", "orange", "pear", "grape", "kiwi"};
System.out.println("Before sorting:");
for (String word : words) {
System.out.print(word + " ");
}
bucketSort(words);
System.out.println("\nAfter sorting (ascending):");
for (String word : words) {
System.out.print(word + " ");
}
}
}
此实现使用第一个字符的 ASCII 值将字符串分配到桶中。然后，在连接之前，每个桶按字母顺序排序。
桶排序 vs 快速排序基准测试
为了比较性能，我们将使用不同的输入大小和分布对桶排序和快速排序进行基准测试。我们将使用 Java 的 System.nanoTime() 进行测量。
SortBenchmark.java
package com.zetcode;
import java.util.Arrays;
import java.util.Random;
public class SortBenchmark {
public static void bucketSort(int[] arr, int bucketSize) {
// Implementation from previous example
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] sizes = {1000, 10000, 100000};
Random random = new Random();
for (int size : sizes) {
System.out.println("\nBenchmark for array size: " + size);
// Uniformly distributed data
int[] uniformData = new int[size];
for (int i = 0; i < size; i++) {
uniformData[i] = random.nextInt(size);
}
// Highly clustered data
int[] clusteredData = new int[size];
for (int i = 0; i < size; i++) {
clusteredData[i] = random.nextInt(size / 10);
}
// Benchmark uniform data
benchmarkSorts(uniformData, "Uniform distribution");
// Benchmark clustered data
benchmarkSorts(clusteredData, "Clustered distribution");
}
}
private static void benchmarkSorts(int[] originalData, String distributionType) {
System.out.println("\n" + distributionType + ":");
// Bucket sort
int[] data = Arrays.copyOf(originalData, originalData.length);
long start = System.nanoTime();
bucketSort(data, 100);
long end = System.nanoTime();
System.out.printf("Bucket sort time: %d ns%n", (end - start));
// Quick sort
data = Arrays.copyOf(originalData, originalData.length);
start = System.nanoTime();
quickSort(data, 0, data.length - 1);
end = System.nanoTime();
System.out.printf("Quick sort time: %d ns%n", (end - start));
}
}
基准测试表明，当数据均匀分布时，桶排序比快速排序表现更好，尤其是在处理更大的数据集时。但是，对于集群数据，快速排序通常优于桶排序。
何时使用桶排序
当输入在范围内均匀分布时，桶排序是理想的选择。当您需要稳定排序（保持相等元素的相对顺序）以及可以承担额外的桶空间时，它也很有用。
对于小型数据集或内存受限时，像插入排序或快速排序这样更简单的算法可能更合适。在选择排序算法时，请始终考虑您的特定用例。
来源
在本文中，我们介绍了 Java 中的桶排序算法，包括数字和文本数据的实现，并将它的性能与快速排序进行了比较。
作者
列出所有Java教程。