Java 基數排序

Java 中的基數排序是一種整數排序演算法，它使用整數鍵並將鍵與共享相同有效位置和位值的各個數字進行分組。然後，元素按照升序/降序排序。基數排序的主要想法是從最低有效位元開始到最高有效位元進行逐位排序。它使用計數排序作為子例程對數字數組進行排序。基數排序結合了計數排序，因此它可以對大數字和多數字進行排序，而不必透過增加演算法排序的鍵範圍來降低其效率。讓我們更深入地研究基數排序，並透過一些範例來了解基數排序在 Java 中的工作原理。

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

文法

基數排序包含如何執行排序的演算法步驟或流程圖。那我們來看看基數排序的演算法。

基數排序演算法

第1步：首先，我們要找出陣列中最大的元素，也就是最大元素。讓我們將 X 視為最大元素中的位數。

我們需要計算 X，因為我們需要遍歷最大元素的位置值。

第 2 步： 現在，我們需要遍歷最大元素的每個位元值。

第3步：我們需要使用任何穩定的排序演算法對每個有效位值處的數字進行排序。

第 4 步： 元素現在依照單位位值 {X=0}

處的數字進行排序

第五步：然後，依照十位數字對元素進行排序{X=10}

第6步：然後，依照百位{X=100}的數字對元素進行排序

第 7 步： 如果陣列中的元素還有更多位置值，即基於 X 值，則重複上述步驟。

Java 中基數排序是如何進行的？

讓我們透過一些例子來看看基數排序是如何實現的。

範例#1

代碼：

import java.util.*;
public class radixSorting {
static int get_maxVal(int radixArr[], int arrLen) {
int maxVal = radixArr[0];
for (int i = 1; i < arrLen; i++)
if (radixArr[i] > maxVal)
maxVal = radixArr[i];
return maxVal;
}
static void countSorting(int radixArr[], int arrLen, int exp) {
int resultArray[] = new int[arrLen];
int i;
int countVal[] = new int[10];
Arrays.fill(countVal,0);
for (i = 0; i < arrLen; i++)
countVal[ (radixArr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
countVal[i] += countVal[i - 1];
for (i = arrLen - 1; i >= 0; i--) {
resultArray[countVal[ (radixArr[i]/exp)%10 ] - 1] = radixArr[i];
countVal[ (radixArr[i]/exp)%10 ]--;
}
for (i = 0; i < arrLen; i++)
radixArr[i] = resultArray[i];
}
static void radix_array_sort(int radixArr[], int arrLen) {
int m = get_maxVal(radixArr, arrLen);
for(int exp = 1; m/exp > 0; exp *= 10)
countSorting(radixArr, arrLen, exp);
}
public static void main (String[] args) {
int radixArr[] = {32,456,71,10,9,892,55,90,23,667};
int arrLen = radixArr.length;
System.out.println("Array after radix sort is ");
radix_array_sort(radixArr, arrLen);
for (int i=0; i<arrLen; i++)
System.out.print(radixArr[i]+" ");
}
}

輸出：

在這裡，我們可以看到輸入數組已使用基數排序和計數排序進行排序。

範例#2

代碼：

import java.util.Arrays;
public class RadixSorting {
public static void sorting(int[] inputArray) {
RadixSorting.sorting(inputArray, 10);
}
public static void sorting(int[] inputArray, int radix) {
if (inputArray.length == 0) {
return;
}
int minVal = inputArray[0];
int maxVal = inputArray[0];
for (int i = 1; i < inputArray.length; i++) {
if (inputArray[i] < minVal) {
minVal = inputArray[i];
} else if (inputArray[i] > maxVal) {
maxVal = inputArray[i];
}
}
int exponentVal = 1;
while ((maxVal - minVal) / exponentVal >= 1) {
RadixSorting.countingSort_by_digit(inputArray, radix, exponentVal, minVal);
exponentVal *= radix;
}
}
private static void countingSort_by_digit(
int[] inputArray, int radix, int exponentVal, int minVal) {
int bucket_index;
int[] bucket = new int[radix];
int[] output = new int[inputArray.length];
for (int i = 0; i < radix; i++) {
bucket[i] = 0;
}
for (int i = 0; i < inputArray.length; i++) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
bucket[bucket_index]++;
}
for (int i = 1; i < radix; i++) {
bucket[i] += bucket[i - 1];
}
for (int i = inputArray.length - 1; i >= 0; i--) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
output[--bucket[bucket_index]] = inputArray[i];
}
for (int i = 0; i < inputArray.length; i++) {
inputArray[i] = output[i];
}
}
public static void main(String args[])
{
RadixSorting rs = new RadixSorting();
int radix_input[] = {72, 15, 30, 21, 13, 944, 417};
System.out.println("Original Input Array:");
System.out.println(Arrays.toString(radix_input));
rs.sorting(radix_input);
System.out.println("Sorted Array using Radix Sort:");
System.out.println(Arrays.toString(radix_input));
}
}

輸出：

所以在這裡，我們使用不同的邏輯來使用基數排序來對輸入數組進行排序。

現在，讓我向您解釋或向您展示如何透過實例進行基數排序，

我們將輸入數組當作 [72, 15, 30, 21, 13, 944, 417]

第 1 步： 從陣列中取得最大值，即 944。因此，現在 X 值為 3，即 X = no。最大元素中的數字，這實際上意味著數組的排列將分三次進行

第2步：所以，現在我們將嘗試根據最低有效數字來排列數字。

考慮到所有元素的單位位置值會重新排列數組，如下所示，

[30、21、72、13、944、15、417]

考慮到所有元素的十位值將重新排列數組，如下所示，

[13、15、417、21、30、944、72]

考慮到所有元素的百位值（如果有），將重新排列數組，如下所示，

[13、15、21、30、72、417、944]

第 3 步：陣列已排序完畢。

結論

至此，我們將結束「Java 中的基數排序」一文。我們已經了解了基數排序是什麼以及它是如何使用計數排序來實現的。它是最簡單的排序形式之一，如果鍵很短，即元素的範圍較小，則速度也會更快。在過去的幾年裡，排序技術已廣泛應用於日常演算法中。然而，也有一些缺點；基數排序在很大程度上取決於輸入，即字母或數字，因此不如其他排序靈活。

以上是Java 基數排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！