Schnelle Sortierung in Java

Der folgende Artikel, Quick Sort in Java, bietet eine Übersicht über den Quick Sort-Algorithmus in Java. Der Schnellsortierungsalgorithmus ist einer der Sortieralgorithmen, der effizient ist und dem Zusammenführungssortierungsalgorithmus ähnelt. Dies ist einer der am häufigsten verwendeten Algorithmen für Echtzeitsortierungszwecke. Die Zeitkomplexität dieses Algorithmus im ungünstigsten Fall beträgt O(n^2), die Zeitkomplexität im durchschnittlichen Fall beträgt O(n log n) und die Zeitkomplexität im besten Fall beträgt O(n log n).

Die Raumkomplexität, wenn O(n log n), wobei n die Größe der Eingabe ist. Der Sortierprozess umfasst die Partitionierung der Eingabe, rekursive Iterationen und die Markierung eines zentralen Elements für jede Rekursion. Die Art der Sortierung in diesem Algorithmus beinhaltet einen iterativen Vergleich benachbarter Elemente.

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Wie funktioniert die Schnellsortierung in Java?

Der Schnellsortierungsalgorithmus kann in Java implementiert werden, indem ein Pseudocode mit einer Abfolge von Schritten gebildet wird, die auf effiziente Weise entworfen und befolgt werden.

• Das Hauptprinzip des schnellen Sortieralgorithmus basiert auf dem Divide-and-Conquer-Ansatz und ist auch ein effizienter Sortieralgorithmus.
• Das Eingabearray ist in Unterarrays unterteilt, und die Aufteilung basiert auf dem Pivot-Element, das ein zentrales Element ist. Die Unterarrays auf beiden Seiten des Pivot-Elements sind die Hauptbereiche, in denen die Sortierung tatsächlich stattfindet.
• Das zentrale Pivot-Element ist die Basis zur Aufteilung des Arrays in zwei Partitionen, wobei die linke Hälfte der Array-Elemente kleiner als das Pivot-Element und die rechte Hälfte der Array-Elemente größer als das Pivot-Element ist.
• Bevor wir das Pivot-Element in Betracht ziehen, kann es sich um jedes beliebige Element eines Arrays handeln. Um das Verständnis zu erleichtern, wird dies normalerweise als mittlerer oder erster oder letzter betrachtet. Das Pivot-Element kann ein zufälliges Element aus einem der Array-Elemente sein.
• In unserem Beispiel wird das letzte Element eines Arrays als Pivot-Element betrachtet, wobei die Partitionierung von Unterarrays am rechten Ende des Arrays beginnt.
• Schließlich befindet sich das Pivot-Element nach Abschluss des Sortiervorgangs in seiner tatsächlichen Sortierposition, wobei der Hauptprozess des Sortierens in der Partitionslogik des Sortieralgorithmus liegt.
• Die Effizienz des Algorithmus hängt von der Größe der Unterarrays und deren Ausgewogenheit ab. Je unausgeglichener die Unterarrays sind, desto größer ist die zeitliche Komplexität, was im schlimmsten Fall zur Komplexität führt.
• Die zufällige Auswahl von Pivot-Elementen führt in vielen Fällen zu der besten Zeitkomplexität, anstatt einen bestimmten Start-, End- oder Mittelindex als Pivot-Elemente auszuwählen.

Beispiele zur Implementierung der Schnellsortierung in Java

Der QuickSort-Algorithmus wurde wie folgt mit der Programmiersprache Java implementiert und der Ausgabecode wurde unter dem Code angezeigt.

• Der Code übernimmt zunächst die Eingabe mithilfe der Methode quickSortAlgo() mit dem Array, dem Anfangsindex und dem Endindex, d. h. der Länge des Arrays, als Argumente.
• Nach dem Aufruf der Methode „quickSortAlgo()“ prüft sie, ob der Anfangsindex kleiner als der Endindex ist, und ruft dann die Methode „arrayPartition()“ auf, um den Wert des Pivot-Elements abzurufen.
• Das Partitionselement enthält die Logik zum Anordnen der kleineren und größeren Elemente basierend auf den Elementwerten um das Pivot-Element.
• Nachdem nach der Ausführung der Partitionsmethode der Pivot-Elementindex abgerufen wurde, wird die Methode quickSortAlgo() selbst rekursiv aufgerufen, bis alle Unterarrays vollständig partitioniert und sortiert sind.
• In der Partitionslogik wird das letzte Element als Pivot-Element zugewiesen und das erste Element mit dem Pivot-Element verglichen, d. h. dem letzten, bei dem die Elemente je nachdem, ob sie kleiner oder größer sind, vertauscht werden.
• Dieser Rekursionsprozess findet statt, bis alle Elemente eines Arrays partitioniert und sortiert sind, wobei das Endergebnis ein kombiniertes sortiertes Array ist.
• Die Elemente werden innerhalb der For-Schleifen-Iteration nur dann ausgetauscht, wenn das Element kleiner oder gleich dem Pivot-Element ist.
• Nach Abschluss des Iterationsprozesses wird das letzte Element ausgetauscht, d. h. der Wert des Pivotelements wird auf die linke Seite verschoben, sodass die neuen Partitionen erstellt werden, und der gleiche Vorgang wiederholt sich in Form einer Rekursion, was zu einer Reihe von führt Sortieroperationen auf verschiedenen möglichen Partitionen als Bildung von Unterarrays aus den gegebenen Array-Elementen.
• Der folgende Code kann auf jeder IDE ausgeführt werden und die Ausgabe kann durch Ändern des Array-Werts in main() überprüft werden. Die Hauptmethode wird nur dazu verwendet, die Ausgabe in der Konsole abzurufen. Als Teil der Java-Codierungsstandards kann die Hauptmethode unten entfernt und ein Objekt erstellt werden. Außerdem können die folgenden Methoden aufgerufen werden, indem sie nicht statisch gemacht werden.

Code-Implementierung des Schnellsortierungsalgorithmus in Java

Es folgt eine Code-Implementierung:

Code:

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}

Ausgabe:

Fazit

Der Schnellsortierungsalgorithmus ist effizient, aber im Vergleich zu anderen Sortiertechniken nicht sehr stabil. Die Effizienz schneller Sortieralgorithmen nimmt ab, wenn eine größere Anzahl wiederholter Elemente vorliegt, was einen Nachteil darstellt. Die Platzkomplexität wird in diesem Schnellsortierungsalgorithmus optimiert.

Das obige ist der detaillierte Inhalt vonSchnelle Sortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!