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中文網其他相關文章！