Java中的桶排序

将给定数组的元素分配到多个桶中，使用不同的排序算法或递归地使用桶排序算法对每个桶进行排序的排序技术在Java中称为桶排序，其空间复杂度为O (1)，最坏情况复杂度为 O(n^2)，最好情况复杂度为 Omega(n+k)，平均情况复杂度为 theta(n+k)，桶排序技术对数组的给定元素进行排序的工作原理与其他排序算法相比，速度更快，并且使用桶排序算法排序的数组元素必须均匀分布。

开始您的免费软件开发课程

网络开发、编程语言、软件测试及其他

Java中进行桶排序的函数如下：

public static int[] bucketsort(int[] array, int maximum_value)
{
int[] newbucket = new int[maximum_value + 1];
int[] sorted_array = new int[array.length];
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}

其中 array 是要使用桶排序算法排序的输入数组，maximum_value 是给定数组中存在的 maximum_value，sorted_array 是由排序元素组成的结果数组。

Java 中桶排序算法的工作原理

Java中桶排序算法的工作原理如下：

• 桶排序算法的第一步是创建一个空数组，该数组被视为桶。
• 第二步是遍历整个要排序的输入数组，并将每个元素添加到桶中。
• 第三步是对桶中的每个元素进行排序。
• 第四步，遍历桶中的所有元素，并将每个元素按排序顺序添加到原始输入数组中。

Java 中桶排序的示例

以下是示例：

示例#1

Java 程序通过实现桶排序算法对给定数组的元素进行排序，然后将排序后的数组元素显示为屏幕上的输出：

 代码：

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

输出：

在上面的程序中，我们创建了一个名为 newbucket 的空数组，它被视为存储桶数组。然后我们创建另一个名为sorted_array 的空数组来存储结果数组。然后我们遍历输入数组，将每个元素添加到存储桶数组中。然后，我们对存储桶数组中的每个元素进行排序，并将每个已排序的元素按顺序添加到原始输入数组中。然后我们定义一个函数来查找输入数组中的最大值，以便使用桶排序技术对给定数组进行排序。然后调用主函数，在其中显示结果数组。输出如上面的快照所示。

示例#2

Java 程序通过实现桶排序算法对给定数组的元素进行排序，然后将排序后的数组元素显示为屏幕上的输出：

代码：

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={ 60, 80, 50, 90, 30, 70, 20 };
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

输出：

在上面的程序中，我们创建了一个称为新存储桶的空数组，它被视为存储桶数组。然后我们创建另一个名为sorted_array 的空数组来存储结果数组。然后我们遍历输入数组，将每个元素添加到存储桶数组中。然后，我们对存储桶数组中的每个元素进行排序，并将每个已排序的元素按顺序添加到原始输入数组中。然后我们定义一个函数来查找输入数组中的最大值，以便使用桶排序技术对给定数组进行排序。然后调用主函数，在其中显示结果数组。输出如上面的快照所示。

以上是Java中的桶排序的详细内容。更多信息请关注PHP中文网其他相关文章！