Bucket Sort in Java

2025年5月3日 | 阅读 6 分钟

桶排序是一种排序技术，其中元素首先被均匀地分成几个称为桶的组。之后，使用任何排序算法对元素进行排序，最后，将元素收集起来形成一个有序的序列。在本节中，我们将学习桶排序的工作原理、其算法、复杂度、示例以及在 Java 程序中的实现。

桶排序

桶排序或箱排序是一种排序算法，它通过将元素均匀地分布到多个桶中来工作。然后对每个桶进行单独排序。为了对桶进行排序，我们使用 Arrays 类的 sort() 方法。它通常用于对浮点数进行排序。

执行桶排序的基本思想是

将范围划分为固定数量的桶。
将每个元素放入其相应的桶中。
使用插入排序单独对每个桶进行排序。
按顺序连接所有已排序的桶。

优点

由于均匀分布，因此在渐近意义上非常快。
它减少了比较次数。
与冒泡排序相比，它更快。

缺点

它不是原地排序，因为我们需要一些额外的空间来排序桶。
它可能是稳定的排序算法，也可能不是。
如果数组很大，它就不是很有用，因为它会增加成本。

让我们看看算法。

算法

Bucket Sort(A[])

让 B[0….n-1] 为一个新数组
n=length[A]
for i=0 to n-1
使 B[i] 为一个空列表
for i=1 to n
将 A[i] 插入列表 B[n a[i]] 中
for i=0 to n-1
使用插入排序对列表 B[i] 进行排序
按顺序连接列表 B[0], B[1],..……, B[n-1]

复杂度

时间复杂度
最坏情况	O(n2)
最佳情况	O(n+k)
平均情况	O(n+k)

桶排序示例

使用桶排序将以下数组按升序排序。

arr[]=22, 45, 12, 8, 10, 6, 72, 81, 33, 18, 50, 14

给定数组中的元素总数 (N) = 12

数组中的最大元素 = 81

数组中的最小元素 = 6

我们需要10个桶来对数组进行排序。假设这 10 个桶由B表示。之后，我们需要找到一个分隔符，用于将元素放入桶中。为了确定分隔符，我们使用以下公式

将值放入上述公式中，我们得到

因此，桶数 = 10，分隔符 = 9

我们将使用以下公式将元素 arr[i] 放入正确的桶中

让我们通过将元素放入桶中来查看它是如何工作的。我们将从第一个索引开始。

对于 i=0

我们将第零个元素(22)插入第 2 个桶，并将数组索引 (i) 增加 1。

对于 i=1

我们将第一个元素(45)插入第 5 个桶，并将数组索引 (i) 增加 1。

对于 i=2

我们将第二个元素(12)插入第 1 个桶，并将数组索引 (i) 增加 1。

对于 i=3

我们将第三个元素(8)插入第 0 个桶，并将数组索引 (i) 增加 1。

对于 i=4

我们将第四个元素(10)插入第 1 个桶，并将数组索引 (i) 增加 1。

对于 i=5

我们将第五个元素(6)插入第 0 个桶，并将数组索引 (i) 增加 1。

对于 i=6

我们将第六个元素(72)插入第 8 个桶，并将数组索引 (i) 增加 1。

对于 i=7

我们将第七个元素(81)插入第 8 个桶，并将数组索引 (i) 增加 1。

对于 i=8

我们将第八个元素(33)插入第 3 个桶，并将数组索引 (i) 增加 1。

对于 i=9

我们将第九个元素(18)插入第 2 个桶，并将数组索引 (i) 增加 1。

对于 i=10

我们将第十个元素(50)插入第 5 个桶，并将数组索引 (i) 增加 1。

对于 i=11

我们将第十一个元素(14)插入第 1 个桶，并将数组索引 (i) 增加 1。

现在，我们将对各个桶执行插入排序以对元素进行排序。让我们从第一个桶（第 0 个）开始。

是否？是的，交换它们的位置。

现在，转到下一个桶（第 1 个），并比较每个元素与其他元素。

是否？是的，交换它们的位置并比较下一对。是否？否，元素已按排序顺序排列，因此我们不会交换它们的位置。

现在，转到下一个桶（第 2 个）并比较它们的元素。

是否？是的，交换它们的位置。

现在，我们将转到下一个桶。在这里，需要注意的是，只有一个元素的桶已经排序，而没有元素的桶将被跳过。因此，我们将转到第五个桶并比较它们的元素。

是否？否，元素已排序。同样，跟踪桶，直到我们到达最后一个桶。因此，我们在这里停止，因为我们已经得到了一个已排序的数组。

最后，我们将从每个桶中取出所有元素。因此，我们得到一个已排序的数组。

我们已经理解了桶排序的逻辑。让我们在 Java 程序中实现该逻辑，并执行数组的桶排序。

桶排序 Java 程序

BucketSortExample1.java

import java.util.*;
public class BucketSortExample1 
{
//user-defined method to sort array
private static void binSort(int[] array, int bucketSize)
{
//creating a list of buckets for storing lists
List<Integer>[] buckets = new List[bktSize];
// Linked list with each bucket array index
// as there may be hash collision 
for(int i = 0; i < bktSize; i++)
{
buckets[i] = new LinkedList<>();
}
//calculate the hash and assigns elements to the proper bucket
for(int num : array)
{
buckets[hash(num, bktSize)].add(num);
}
//iterate over the buckets and sorts the elements
for(List<Integer> bucket : buckets)
{
//sorts the bucket    
Collections.sort(bucket);
}
int index = 0;
//gethered the buckets after sorting
for(List<Integer> bucket : buckets)
{
for(int num : bucket)
{
array[index++] = num;
}
}
}
//distributing elements 
private static int hash(int num, int bucketSize)
{
return num/bucketSize;
}
public static void main(String args[]) 
{
//array to be sort    
int[] array = {22, 45, 12, 8, 10, 6, 72, 81, 33, 18, 50, 14, 55, 0, 12, 55};
System.out.println("Unsorted Array: " + Arrays.toString(array));
//calling the user-defined method to sort the array
binSort(array, 10);
System.out.println("Sorted Array: " + Arrays.toString(array));
}
}

输出

Unsorted Array: [22, 45, 12, 8, 10, 6, 72, 81, 33, 18, 50, 14, 55, 0, 12, 55]
Sorted Array: [0, 6, 8, 10, 12, 12, 14, 18, 22, 33, 45, 50, 55, 55, 72, 81]

让我们创建另一个 Java 程序，该程序随机生成数组元素并使用桶排序对它们进行排序。

BucketSortExample2.java

import java.util.*;
public class BucketSortExample2
{
//user-defined method that sorts the array elements    
static int[] bucketSort(int[] array, int maxValue) 
{
//createsa buckets array
int[] Bucket = new int[maxValue + 1];
//creating an array for storing the sorted elements
int[] sorted_array = new int[array.length];
for (int i = 0; i < array.length; i++)
Bucket[array[i]]++;
int outPos = 0;
for (int i = 0; i < Bucket.length; i++)
for (int j = 0; j < Bucket[i]; j++)
sorted_array[outPos++] = i;
//returns sorted array
return sorted_array;
} 
//method that prins the array elements 
static void printArray(int[] sorted_array) 
{
for (int i = 0; i < sorted_array.length; i++)
System.out.print(sorted_array[i] + " ");
}
//method finds the maximum elements of the array and returns the same
static int maxValue(int[] array) 
{
int maxValue = 0;
for (int i = 0; i < array.length; i++)
if (array[i] > maxValue)
maxValue = array[i];
return maxValue;
}
//driver code
public static void main(String args[]) 
{
System.out.println("Sorted array after performing bucket sort:");
Random random = new Random();
//the number of elements to be randomly generate
int N = 12;
//creating an array of randomly generated numbers (N)
int[] array = new int[N];
for (int i = 0; i < N; i++)
//generates random numbers within specified range i.e. 40
array[i] = Math.abs(random.nextInt(40));
//determines the maximum value in the array
int maxValue = maxValue(array);
System.out.println("\nUn-sorted Array: ");
//prints un-sorted array
printArray(array);
System.out.println("\nSorted Array: ");
//prints sorted array
printArray(bucketSort(array, maxValue));
}
}

输出

Sorted array after performing bucket sort:

Un-sorted Array: 
16, 1, 0, 6, 14, 4, 22, 19, 37, 34, 17, 39
Sorted Array: 
0, 1, 4, 6, 14, 16, 17, 19, 22, 34, 37, 39

下一个主题Java-检测链表中循环的程序

Bucket Sort in Java

桶排序

优点

缺点

算法

复杂度

桶排序示例

桶排序 Java 程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Bucket Sort in Java

桶排序

优点

缺点

算法

复杂度

桶排序示例

桶排序 Java 程序

相关帖子

Java 8 和 Java 11 的区别

Keytool 错误 java.io.IOException 格式不正确

Java 中的单词搜索问题

Remove Loop in Linked List Using Java

Java 中的 Kynea 数

Java 中用于先序遍历的 Morris 遍历

How to Remove Last Character from String in Java

Java 的 Kalangs 是谁

Java 中的 final 数组

Java FileInputStream finalize() 方法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器