HOWTO · Java
Java 基數排序演算法
本教程詳細解釋了基數排序演算法並演示了 Java 中的實現。
本頁內容
在基數排序演算法中，元素的排序首先將具有相同位值的單個數字分組，然後按照升序或降序排序。本教程詳細解釋了基數排序演算法，並演示了 Java 中基數排序的實現。
基數排序演算法
按照以下步驟應用基數排序。
- 首先從輸入陣列中找到最大元素；然後，該最大數量將用於遍歷所有陣列成員的重要位置。
- 接下來，一個一個地走過每個重要的地方。我們可以使用任何穩定的排序演算法，例如計數排序，對每個重要位置的元素進行排序。
支援六個元素的陣列。radix sort 將首先根據單位位置的值對元素進行排序。
然後根據第十位的值對陣列的元素進行排序。
假設陣列是 [9, 50, 4, 203, 17, 39]。下圖顯示了這個陣列根據 radix sort 進行了多次排序。
基數排序演算法的時間複雜度
下表顯示了 radix sort 演算法在不同情況下的時間複雜度。
| 時間複雜度 | 情況 |
|---|---|
Ω(n+k) |
最佳情況 |
θ(nk) |
平均情況 |
O(nk) |
最差情況 |
- 最佳情況 - 當不需要排序時，陣列已經排序。在最佳情況下，
基數排序時間複雜度是Ω(n+k)。 - 平均情況 - 陣列元素的順序混亂，沒有正確的降序或升序。在平均情況下，
基數排序時間複雜度是θ(nk)。 - 最壞情況 - 當陣列元素必須以相反的順序排序時，例如從升序到降序或從降序到升序。在最壞的情況下，
基數排序時間複雜度是O(nk)。
基數排序演算法的虛擬碼
基數排序演算法的虛擬碼如下。
Radix_Sort(Input_Array)
MAX = largest number in the input array
DIGIT = number of digits in the largest number
Now, create DIGIT buckets of size 0 - 9
for x -> 0 to DIGIT
sort the elements according to any stable sort
Java 中的基數排序演算法實現
使用計數排序，讓我們實現基數排序演算法。參見示例：
package delftstack;
import java.util.Arrays;
public class Radix_Sort {
public static void main(String args[]) {
int[] input_array = {9, 50, 4, 203, 17, 39};
int array_size = input_array.length;
Radix_Sort RadixSort = new Radix_Sort();
RadixSort.Radix_Sort(input_array, array_size);
System.out.println("Sorted Array Using Radix Sort: ");
System.out.println(Arrays.toString(input_array));
}
// Counting sort to sort the elements on the basis of significant places
void Counting_Sort(int input_array[], int array_size, int number_place) {
int[] output_array = new int[array_size + 1];
int max_number = input_array[0];
for (int x = 1; x < array_size; x++) {
if (input_array[x] > max_number) {
max_number = input_array[x];
}
}
int[] count_array = new int[max_number + 1];
for (int x = 0; x < max_number; ++x) {
count_array[x] = 0;
}
// Calculating the count of elements
for (int x = 0; x < array_size; x++) {
count_array[(input_array[x] / number_place) % 10]++;
}
// Calculating the cumulative count
for (int x = 1; x < 10; x++) {
count_array[x] += count_array[x - 1];
}
// Sorting the elements
for (int x = array_size - 1; x >= 0; x--) {
output_array[count_array[(input_array[x] / number_place) % 10] - 1] = input_array[x];
count_array[(input_array[x] / number_place) % 10]--;
}
for (int x = 0; x < array_size; x++) {
input_array[x] = output_array[x];
}
}
// Get the largest element from input array
int Get_Max(int input_array[], int array_size) {
int max_number = input_array[0];
for (int i = 1; i < array_size; i++) {
if (input_array[i] > max_number) {
max_number = input_array[i];
}
}
return max_number;
}
// Implement the radix sort
void Radix_Sort(int input_array[], int array_size) {
// Get the maximum number
int max_number = Get_Max(input_array, array_size);
// Apply the counting sort based on significant place value.
for (int number_place = 1; max_number / number_place > 0; number_place *= 10) {
Counting_Sort(input_array, array_size, number_place);
}
}
}
上面的程式碼在 counting sort 的幫助下實現了基數排序。見輸出：
Sorted Array Using Radix Sort:
[4, 9, 17, 39, 50, 203]
