Radix-Sortierung in Java ist ein ganzzahliger Sortieralgorithmus, der ganzzahlige Schlüssel verwendet und die Schlüssel mit einzelnen Ziffern gruppiert, die dieselbe signifikante Position und denselben Stellenwert haben. Anschließend werden die Elemente in aufsteigender/absteigender Reihenfolge sortiert. Die Hauptidee der Radix-Sortierung besteht darin, Ziffer für Ziffer von der niedrigstwertigen bis zur höchstwertigen Ziffer zu sortieren. Es verwendet die Zählsortierung als Unterroutine, um ein Array von Zahlen zu sortieren. Die Radix-Sortierung beinhaltet eine Zählsortierung, so dass große und mehrstellige Zahlen sortiert werden können, ohne dass die Effizienz dadurch beeinträchtigt werden muss, dass der Schlüsselbereich vergrößert wird, den der Algorithmus sortieren würde. Lassen Sie uns tiefer in die Radix-Sortierung eintauchen und anhand einiger Beispiele sehen, wie die Radix-Sortierung in Java funktioniert.
Starten Sie Ihren kostenlosen Softwareentwicklungskurs
Webentwicklung, Programmiersprachen, Softwaretests und andere
Syntax
Die Radix-Sortierung verfügt über Algorithmusschritte oder ein Flussdiagramm zur Durchführung der Sortierung. Schauen wir uns also den Algorithmus der Radix-Sortierung an.
Schritt 1:Zuerst müssen wir das größte Element im Array finden, d. h. das maximale Element. Und betrachten wir X als die Anzahl der Ziffern im maximalen Element.
Wir müssen X berechnen, da wir den Stellenwert eines maximalen Elements durchgehen müssen.
Schritt 2:Jetzt müssen wir jeden Stellenwert des maximalen Elements durchgehen.
Schritt 3:Wir müssen einen beliebigen stabilen Sortieralgorithmus verwenden, um Ziffern an jedem signifikanten Stellenwert zu sortieren.
Schritt 4:Elemente werden nun nach Ziffern am Einheitenstellenwert {X=0}
sortiertSchritt 5:Anschließend sortieren Sie die Elemente nach den Ziffern an der Zehnerstelle {X=10}
Schritt 6:Sortieren Sie dann die Elemente anhand der Ziffern an der Hunderterstelle {X=100}
Schritt 7:Der obige Schritt wird wiederholt, wenn weitere Stellenwerte für Elemente im Array vorhanden sind, d. h. basierend auf dem X-Wert.
Lassen Sie uns anhand einiger Beispiele überprüfen, wie die Radix-Sortierung implementiert wird.
Code:
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
Nach dem Login kopieren
Ausgabe:
Hier können wir also sehen, dass das Eingabearray mithilfe der Radix-Sortierung zusammen mit der Counting-Sortierung sortiert wurde.
Code:
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)); } }
Ausgabe:
Hier verwenden wir also eine andere Logik, um das Eingabearray mithilfe der Radix-Sortierung zu sortieren.
Jetzt möchte ich Ihnen anhand eines Live-Beispiels erklären oder zeigen, wie die Radix-Sortierung durchgeführt wird.
Wir nehmen das Eingabearray als [72, 15, 30, 21, 13, 944, 417]
Schritt 1:Holen Sie sich den Maximalwert aus dem Array, d. h. 944. Der X-Wert wäre jetzt also 3, d. h. X = nein. Anzahl der Ziffern im Maximum-Element, was tatsächlich bedeutet, dass die Anordnung des Arrays dreimal erfolgen würde
Schritt 2:Nun werden wir versuchen, Zahlen auf der Grundlage der niedrigstwertigen Ziffer anzuordnen.
Wenn man den Stellenwert der Einheit aller Elemente berücksichtigt, wird das Array wie folgt neu angeordnet,
[30, 21, 72, 13, 944, 15, 417]Unter Berücksichtigung der Zehnerstellenwerte aller Elemente wird das Array wie folgt neu angeordnet:
[13, 15, 417, 21, 30, 944, 72]Unter Berücksichtigung des Hunderterstellenwerts aller Elemente, falls vorhanden, wird das Array wie folgt neu angeordnet,
[13, 15, 21, 30, 72, 417, 944]Schritt 3:Damit sind die Arrays sortiert.
Damit schließen wir den Artikel „Radix-Sortierung in Java“ ab. Wir haben gesehen, was Radix-Sortierung ist und wie sie mithilfe der Zählsortierung implementiert wird. Es handelt sich um eine der einfachsten Sortierformen und ist außerdem schneller, wenn die Schlüssel kurz sind, d. h. der Bereich der Elemente geringer ist. In den letzten Jahren wurden Sortiertechniken in großem Umfang in die tägliche algorithmische Nutzung integriert. Allerdings gibt es auch einige Nachteile; Die Radix-Sortierung hängt stark von der Eingabe ab, d. h. Buchstaben oder Ziffern, und ist daher weniger flexibel als andere Sortierungen.
Das obige ist der detaillierte Inhalt vonRadix-Sortierung Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
