Im Vergleich zu Algorithmen wie Blasensortierung, Sortieren von Selektionen usw. sind die spezifischen Algorithmusprinzipien und die Umsetzung der schnellen Sortierung schwierig. Um die schnelle Sortierung besser zu verstehen, beschreiben wir immer noch die algorithmischen Prinzipien der schnellen Sortierung in Form von Beispielen. Im vorherigen Sortieralgorithmus werden wir das Höhensortierproblem von 5 Athleten als Beispiel verwenden, um dies zu erklären. Um die Eigenschaften der schnellen Sortierung besser widerzuspiegeln, werden wir hier 3 weitere Athleten hinzufügen. Die 8 Athleten und ihre Höheninformationen im Beispiel sind wie folgt (f, g, h sind neue Athleten): A (181), B (169), C (187), D (172), E (163), F (191), G (189), H (182)
Im vorherigen Sortieralgorithmus wurden diese Angaben alle vom Trainer gemacht. Nachdem die Zahl der Athleten zugenommen hat, möchte der Trainer auch die Gelegenheit nutzen, um eine Pause einzulegen, und der Trainer rief zwei Assistenten an und bat die beiden Assistenten, die Höhen der 8 Athleten von links nach rechts und niedrig auf eine schnelle Art zu sortieren.
Nach dem Algorithmusprinzip der Schnellsortiermethode stehen die beiden Assistenten auf beiden Seiten der Anordnung des Athleten, wie in der folgenden Abbildung gezeigt:
Zunächst wählt Assistant 1 einen Athleten aus der Arrangement aus (wählt normalerweise den ersten Athleten links oder den mittleren Athleten aus) und wählt hier den Athleten A (181) aus. Da die Sortierung von links nach rechts und von niedrig bis hoch ist, benötigt Assistant 1 einen Athleten, der kleiner ist als A (181) (der ausgewählte A (181) wird als Benchmark für Vergleiche verwendet. Alle Vergleiche in dieser Runde werden mit dem ursprünglich ausgewählten Athleten A (181) verglichen):
Beziehen wir uns weiterhin auf das detaillierte Diagramm der ersten Runde der schnellen Sortierung.
Wenn sich die beiden Assistenten während des Sortier- und Suchprozesses treffen, wird der Vergleich der aktuellen Runde gestoppt und der ursprünglich ausgewählte Athlet A (181) in den leeren Raum platziert, an dem sich die beiden Assistenten treffen:
In der schnellen Art endet diese Runde, wenn sich zwei Assistenten treffen. Zu diesem Zeitpunkt stellten wir fest, dass die Verwendung der Position A (181), bei der sich die beiden Athleten als Divisionspunkt trafen, die linken Athleten sind, die kleiner als A (181) sind, und die auf der rechten Seite sind Athleten, die größer als A sind (181). Zu diesem Zeitpunkt werden wir die beiden Sorten auf der linken und rechten Seite eines (181) trennen. Wenn wir die Arrangements weiterhin auf beiden Seiten anhand der Sortiermethoden der beiden Assistenten sortieren, erhalten wir nach mehreren Arrangements endlich die Sortierergebnisse, die wir benötigen.
Das obige ist der gesamte Sortier -Implementierungsprozess der schnellen Sortierung. Schnellsortieren besteht darin, die oben genannten Sortierregeln zu verwenden, um eine Vereinbarung in zwei Arrangements zu unterteilen, und die beiden Arrangements in vier Arrangements, bis keine Anordnung geteilt wird, und schließlich erhalten wir das Sortierungsergebnis, das wir benötigen.
Jetzt programmieren wir den Java -Code immer noch, um die Höhen der oben genannten 8 Athleten mit der schnellen Sortierung zu sortieren:
/*** Schnelles Sortieren der Elemente im angegebenen Array von Start bis Ende** @param Array Das angegebene Array* @param Starten Sie den resultierenden Punkt der Array -Anfrage, die schnell sortiert werden muss* @param Ende Das Ende des Array -Index muss schnell sortiert werden. Äquivalent zur Position von Assistant 2 int i = start, j = Ende; int pivot = array [i]; // Nehmen Sie das erste Element als Referenzelement intleeIndex = i; // Der Positionsindex des leeren Raums ist angegeben, und die Standardeinstellung ist die Position des Referenzelements, das abgerufen wird // Wenn es mehr als 1 Elemente zum Sortieren gibt, geben Sie eine schnelle Sortierung ein (solange ich und j unterschiedlich sind, bedeutet dies, dass mindestens 2 Array-Elemente sortiert werden müssen, während (i <j) {// Assistent 2 beginnt, nach Elementen kleiner zu suchen. Wenn (i <j) {// Wenn Assistent 2 vor dem Begegnung Assistant 1 das entsprechende Element findet, gibt es das Element den "freien Stellen" des Assistenten 1, J wird zu einem leeren Raum -Array [leereIndex] = Array [leereIndex = j]; } // Assistant 1 beginnt nach Elementen zu suchen, die größer als das Referenzelement von links nach rechts sind (i <j && array [i] <= pivot) i ++; Wenn (i <j) {// Wenn Assistent 1 das entsprechende Element vor der Begegnung von Assistant 2 findet, gibt es das Element den "freien Stellen" von Assistant 2 und ich werde zu einem freien Array [leereIndex] = Array [leereIndex = i]; }} // Nach Assistent 1 und Assistant 2 Begegnung wird die Schleife gestoppt und der anfängliche Referenzwert wird an das letzte freie Array [leereIndex] = Pivot gebracht; // ===== Diese schnelle Sortierung ist abgeschlossen. } // Wenn es auf der rechten Seite des Split -Punkts j mehr als 2 Elemente gibt, sortiert der rekursive Anruf ihn weiterhin, wenn (Ende - J> 1) {QuickSort (Array, J + 1, Ende); }}//Main method public static void main(String[] args) { // =====Sort from low to high using quick sort method to represent the heights of 8 athletes ===== // A(181), B(169), C(187), D(172), E(163), F(191), G(189), H(182) int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182}; // Rufen Sie die Quick -Sort -Methode QuickSort (Heights, 0, Heights.Length - 1) an; // Ausgabe sortiertes Ergebnis für (int Höhe: Höhen) {System.out.println (Höhe); }}Die obigen Java -Code -Run -Ergebnisse werden wie folgt ausgegeben:
163169172181182187189191
Hinweis: Aufgrund lokaler Denkunterschiede kann es in der obigen schnellen Code -Implementierung mehrere Variationen geben. Unabhängig davon, welche Varianten sind, ändert sich die Kernidee der schnellen Sortierung nicht.
Eine weitere Implementierung: Einwegscanning
Es gibt eine weitere One-Way-Scan-Version für das schnelle Sortieren von Array-Schneiden. Der spezifische Schritt besteht darin, das letzte Element im Array als Schnittelement auszuwählen und zwei Zeiger festzulegen. Der Zeiger, den ich auf eine Position vor dem ersten Element im Array verweist, und J zeigt auf das erste Element im Array. J scannt von vorne nach rechts und rechts. Wenn Sie ein Schnittelement weniger als oder gleich begegnen, fügen Sie i zu einem zu und tauschen Sie dann die Elemente aus, auf die I und J gezeigt wurden. Tauschen Sie schließlich die Elemente an Position I+1 und die Schnittelemente aus, um die Array -Division zu vervollständigen. Die Code -Implementierung ist wie folgt:
int partition (int [] a, int lo, int hi) {int i = lo - 1, j = lo; int v = a [hi]; while (j <hi) {if (a [j] <= v) {swap (a, ++ i, j); } J ++; } Swap (a, i + 1, hi); return i + 1;}