Java Quicksort -Prinzip und Implementierungscode

Quicksort ist ein häufig verwendeter, effizienterer Sortieralgorithmus und wird während des Interviewprozesses häufig erwähnt. Erklären wir seine Prinzipien im Detail und geben wir eine Implementierung von Java -Versionen an.

Schnelle Sortieridee:

Zwei unabhängige Teile werden durch Sortieren des Datenelements -Set RN in einer Reise geteilt. Ein Teil des Schlüsselworts ist kleiner als der andere Teil. Sortieren Sie dann die Schlüsselwörter der beiden Teile nacheinander, bis es nur ein unabhängiges Element gibt, und die gesamte Elementsammlung ist in Ordnung.

Der Prozess der schnellen Sortierung - die Methode zum Graben von Löchern und Ausfüllungsnummern (dies ist ein sehr lebendiger Name) für ein Element -Set R [niedrig ... hoch], nehmen Sie zunächst eine Zahl (normalerweise r [niedrig]) als Referenz und r [niedrig] ordnet alle Elemente als Benchmark um.

Alle kleineren als r [niedrig] werden vorne platziert, all die größer als r [niedrig] werden in den Rücken platziert, und dann wird R [niedrig] als Grenze verwendet, und R [niedrig ... hoch] ist in zwei Untergruppen unterteilt und dann geteilt. Bis niedrig> = hoch.

Zum Beispiel: Der Prozess der Durchführung einer schnellen Sortierung von r = {37, 40, 38, 42, 461, 5, 7, 9, 12} lautet wie folgt (Anmerkung: Die folgende Tabelle der unten beschriebenen Elemente beginnt ab 0):

Wählen Sie die Basisbasis = 37, die folgende Tabelle ist niedrig = 0, hoch = 8, beginnend von hoch = 8, wenn r [8] <Basi Die Position ist leer, niedrig = niedrig +1;

Schreiben Sie von niedrig, da niedrig = 1, R [niedrig]> Basis, r [niedrig] bis r [hoch], hoch = hohe -1;

Niedrig <hoch wird erkannt, sodass die erste schnelle Sortierung weiterhin fortgesetzt werden muss:

Zu diesem Zeitpunkt niedrig = 1, hoch = 7, weil r [hoch] <base, r [hoch] in r [niedrig], niedrig = niedrig + 1;

Starterkennung von niedrig, niedrig = 2, r [niedrig]> Base, so dass r [niedrig] auf r [hoch] geschrieben ist, hoch = hoch-1;

Weiter zu erkennen, dass niedrig ist, ist weniger als hoch ist

Zu diesem Zeitpunkt niedrig = 2, hoch = 6, ähnlich, r [hoch] <base, schreiben r [hoch] bis r [niedrig], niedrig = niedrig+1;

Weiter aus dem niedrigen, niedrigen = 3, hoch = 6, r [niedrig]> Basis, schreiben Sie r [niedrig] bis r [hoch], hoch = hoch-1;

Stellen Sie weiter fest, dass das Tiefst

Zu diesem Zeitpunkt niedrig = 3, hoch = 5, ähnlich, r [hoch] <base, schreiben r [hoch] in r [niedrig], niedrig = niedrig +1;

Weitere Sonde von niedrig, niedrig = 4, hoch = 5, weil r [niedrig]> Basis r [niedrig] in r [hoch], hoch = hohe -1;

Zu diesem Zeitpunkt wird niedrig == hoch == 4 wird erkannt;

Führen Sie dann eine schnelle Sortierung von Untersequenzen RS1 = {12,9,7,5} und RS2 = {461,42,38,40} durch, bis nur ein Element in RSI oder kein Element vorhanden ist.

(Hinweis: In der obigen Form können Sie feststellen, dass die Sortierung einige doppelte Daten gibt (keine doppelten Daten in den ursprünglichen Daten). Dies liegt daran, dass die Daten an diesem Ort nicht gelöscht werden. Wir betrachten die Daten des Speichers Blockieren Sie zu einem bestimmten Zeitpunkt.

Schnelle Sortier -Java -Implementierung:

Die Codekopie lautet wie folgt:

private statische boolean isempty (int [] n) {

return n == null || n.length == 0;

}

// //////////////// .////////// ./////////////// .////////// .//////////. ///

/**

* Schnelle Sortieralgorithmus -Idee - Methode zum Graben von Löchern und Füllen:

*

* @param n Array, um sortiert zu werden

*/

public static void Quicksort (int [] n) {

if (isempty (n))

zurückkehren;

QuickSort (N, 0, N. Length - 1);

}

public static void Quicksort (int [] n, int l, int h) {

if (isempty (n))

zurückkehren;

if (l <h) {

int pivot = partition (n, l, h);

Quicksort (N, L, Pivot - 1);

QuickSort (N, Pivot + 1, H);

}

}

private statische Int -Partition (int [] n, int start, int End) {

int tmp = n [start];

while (starten <end) {

while (n [end]> = tmp && starten <end)

Ende--;

if (starten <end) {

n [start ++] = n [Ende];

}

while (n [starten] <tmp && starten <end)

Start ++;

if (starten <end) {

n [Ende-] = n [Start];

}

}

n [start] = tmp;

Rückkehr;

}

Es gibt eine solche Funktion im Code:

Die Codekopie lautet wie folgt:

öffentliche statische Leere Quicksortswap (int [] n, int l, int h)

Diese Funktion kann implementiert werden, um Datenelemente im Element zwischen spezifischen L- und H -Positionen zu sortieren.

Das ist alles zum schnellen Sortieren.