Quick Sort ist eine Art Division Exchange -Sort, die Crahoare im Jahr 1962 vorgeschlagen hat. Die Grundidee dieser Methode ist:
1. Nehmen Sie zuerst eine Zahl aus der Sequenz als Referenznummer.
2. Setzen Sie im Partitionierungsprozess alle Zahlen größer als diese Zahl nach rechts und alle Zahlen kleiner oder gleich links.
3. Wiederholen Sie den zweiten Schritt für die linken und rechten Intervalle, bis in jedem Intervall nur eine Zahl vorhanden ist.
Der Algorithmus hat eine klare Idee, aber wenn der Grenzwert während des Intervall -Abteilungsprozesses nicht gut behandelt wird, ist es einfach, Fehler zu verursachen. Im Folgenden sind zwei klarere Gedanken, um das Schreiben des Intervallabteilungscode zu leiten.
Die erste Art des Denkens ist die sogenannte Pit-Digging-Methode. Im Folgenden ist die Analyse des Prozesses der Grubengrabenmethode durch Analyse eines Beispiels:
Wenn Sie als Beispiel ein Array nehmen, nehmen Sie die erste Nummer in das Intervall als Referenznummer.
Anfangs, links = 0; rechts = 9; X = a [links] = 72
Da die Zahl in einem [0] in X gespeichert wurde, kann sie als das Graben eines Lochs in das Array A [0] gespeichert werden und andere Daten können hier ausgefüllt werden.
Beginnen Sie von rechts und suchen Sie nach einer Anzahl von <= x. Wenn rechts = 8, wenn die Bedingungen erfüllt sind, graben Sie ein [8] aus und füllen Sie es in die vorherige Grube a [links]. Eine solche Grube A [0] ist gelöst, aber es wird eine neue Grube A [8] gebildet. Was soll ich tun? Einfach, finden Sie die Nummer, um die Grube A [8] zu füllen. Beginnen Sie diesmal von links und finden Sie eine Zahl, die größer als X ist. Wenn Sie links = 3 sind, erfüllen Sie die Bedingungen, graben Sie eine [3] aus und füllen Sie sie in der vorherigen Grube a [rechts].
Das Array wird:
Wiederholen Sie die obigen Schritte und das endgültige Array wird zum folgenden Formular:
Es ist ersichtlich, dass die Zahlen vor A [5] kleiner sind als sie und die Zahlen nach einem [5] größer als sie. Füllen Sie X in die Grube eines [5] und die Daten werden:
Wiederholen Sie daher die obigen Schritte für die beiden Unterintervalle A [0… 4] und A [6… 9].
Zusammenfassung der Anzahl der gegrabenen Löcher
1. i = l; J = r; Graben Sie die Referenznummer aus, um die erste Grube A [i] zu bilden.
2. J-von der Rückseite nach vorne finden Sie die Zahl kleiner als sie, graben Sie diese Nummer heraus und füllen Sie die vorherige Grube A [i] aus.
3. i ++ findet eine Zahl, die größer als sie von vorne nach hinten ist, und graben Sie diese Zahl nach dem Finden aus und füllen Sie sie in der vorherigen Grube A [j].
4. Wiederholen Sie die Schritte 2 und 3 bis i == j, und füllen Sie die Referenznummer in ein [i] aus.
Befolgen Sie diese Partitionsmethode, der Java -Code wird schnell wie folgt sortiert:
öffentliche Klassenpartition { / ** * Basierend auf der Basisdivision ist die kleine links und die große rechts und die gesamte Sequenz muss nicht bestellt werden int right = ary.length - 1; int links = links, rechter Punkt = rechts; while (true) {// gleichzeitig nach links und rechts nach rechts, um zu vergleichen, von links nach rechts, während (linkspitzel <rechts && ary [links ++] <Basis); // LINKTPOPPE ist größer als rechts oder ary [links]> Basis stoppt, dass sie looping (rechter Punkt> = links && ary [RightPoint--]> Basis); // auf dem entgegengesetzten System.out.println ("Der Index muss links ausgetauscht werden:" + (Leftpoint-1)); System.out.println ("Der Index, der rechts ausgetauscht werden muss:"+ (RightPoint+ 1)); // Die beiden Indizes, die den oben genannten Bedingungen nicht erfüllen, werden die beiden Indizes, die if (links - 1 <RightPoint + 1) {// Swap (Ary, Linkspunkt - 1, RightPoint + 1), getauscht werden müssen; Util.printarray (ary); links = links; RightPoint = rechts; } else {break; }}} privater statischer void Swap (int [] ary, int a, int b) {int temp = ary [a]; ary [a] = ary [b]; ary [b] = temp; } public static void main (String [] args) {int [] ary = util.generateIntArray (10); System.out.println ("Originalsequenz:"); Util.printarray (ary); sortieren (ary, 5); System.out.println ("sortiert:"); Util.printarray (ary); }} Ergebnis:
Original sequence: [2, 8, 4, 3, 7, 5, 1, 9, 0, 6] Index to exchange on the left: 1 Index to exchange on the right: 8 [2, 0, 4, 3, 7, 5, 1, 9, 8, 6] Index to exchange on the left: 4 Index to exchange on the right: 6 [2, 0, 4, 3, 1, 5, 7, 9, 8, 6] Index to exchange on the left: 5 Index to exchange on the right: 5 After Sortierung: [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
Ein weiteres leitendes Denken der Intervallabteilung:
Verwenden Sie das erste Element des Arrays als Intervallwert und partitionieren Sie es vom zweiten Element, bis das in der Abbildung gezeigte Ergebnis gebildet ist.
Tauschen Sie dann die rechten Grenzwerte und t des L <t -Intervalls aus, um das folgende Ergebnis zu bilden:
Auf diese Weise können Sie einen schnellen Sortiercode wie folgt schreiben:
public void qsort (int array [], int links, int rechts) {if (links <rechts) {int key = array [links]; int hoch = rechts; int niedrig = links+1; while (true) {while (niedrig <= hoch && array [niedrig] <= key) niedrig ++; while (niedrig <= hoch && array [hoch]> = key) hoch--; wenn (niedrig> hoch) brechen; Swap (Array, niedrig, hoch); } Swap (Array, links, hoch); printArray (Array); QSORT (Array, links, High-1); QSORT (Array, hoch+1, rechts); }}