Java 基數排序演算法
Sheeraz Gul
2023年1月30日
2022年5月1日
在基數排序演算法中，元素的排序首先將具有相同位值的單個數字分組，然後按照升序或降序排序。本教程詳細解釋了基數排序演算法，並演示了 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]
Author: Sheeraz Gul
Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.
LinkedIn Facebook