Zeitkomplexität
Durchschnitt: O (NLGN)
Der schlimmste Fall: O (n*n), tritt auf, wenn sich die Daten bereits im Sortierstatus befinden.
1. Wählen Sie einen Wert A [i] aus den Daten als Referenz aus
2. Teilen Sie die Daten in 2 Teile ein: p1 und p2. Alle Daten in p1 ≤ A [i], alle Daten in P2> a [i] und die Daten werden zu {{P1} {a [i]} {p2}}
3. Wiederholen Sie die obigen Schritte mit P1 und P2, bis in jedem Teil nur 1 Daten übrig sind.
4. Die Daten werden in aufsteigender Reihenfolge sortiert
Grundlegendes Beispiel:
Rohdaten:
{3, 9, 8, 5, 2, 1, 6} Schritt 1: Wählen Sie die ersten Daten aus: 3
Schritt 2: Teilen Sie die Daten in 2 Teile, die linke Seite ist ≤3 und die rechte Seite ist größer als> 3:
{2,1} {3} {9,8,5,6} Schritt 3: Wiederholen Sie die obigen Schritte für jeden Teil, bis in jedem Teil nur 1 Daten übrig sind:
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8} {9} Schritt 4: Die Daten werden in aufsteigender Reihenfolge sortiert:
{1} {2} {3} {5} {6} {8} {9}Die Daten im Programm werden normalerweise in einem Array gespeichert. Wenn Sie als Beispiel ein Array von Typ in INT nutzen, können Sie die obigen Schritte in einen QuickSort -Funktionsprototyp schreiben:
QuickSort (int begin, int End) {// Begin ist der Indexwert der ersten Daten des Arrays. Das Ende ist der Indexwert der letzten Daten des Array +1 //, wenn nur 1 Daten oder 0 Daten vorhanden sind. Das Programm gibt zurück, wenn (begin == end || begin == (end-1)) Return; int p = in [begin]; // p sind die ausgewählten Referenzdaten, wählen Sie die ersten Daten int a = starten +1; // A als Indexwert der 2-teiligen Datenteilungszeile int b = a; // b ist der Indexwert der Daten, für die (; b <end; b ++) {// die Daten im Array mit den Referenzdaten in Sequenz (in [b] <p) {// if die Daten <Referenzdaten, vergleiche, zu links in [a == b) {A ++; Fortsetzung;} // Wenn die Daten bereits links sind, verschiebt sie in [a] die Daten in [a] = in [b]; in [b] = temp; a ++; // Verschieben Sie die Trennlinie rechts}} in [begin] = in [a-1]; // woke den Referenzwert auf die Mitte von 2 Datensätzen in [a-1] = p; Wenn (a-1> begin) {// Wenn links Daten vorhanden sind, wiederholen Sie die obigen Schritte QuickSort (beginnen, a); } if (end-1> a) {// Wenn auf der rechten Seite Daten vorhanden sind, wiederholen Sie die obigen Schritte QuickSort (a, Ende); } zurückkehren; // Wenn es keine Daten gibt} Algorithmusoptimierung
Der obige Schnellsortalgorithmus kann als die grundlegendste schnelle Sortierung bezeichnet werden, da keine Eingabedaten berücksichtigt werden. Es ist jedoch leicht, die Mängel dieses Algorithmus zu finden: Dies ist, wenn unsere Eingabedaten im Grunde genommen geordnet oder sogar vollständig geordnet sind, degeneriert der Algorithmus in Blasensortierung, nicht mehr o (nn), sondern O (n^2).
Die Hauptursache ist, dass wir in unserer Code -Implementierung nur vom ersten Array gleichzeitig beginnen. Wenn wir den "Drei-Header" verwenden, dh die Medianwerte von arr [niedrig], arr [hoch], arr [(niedrig+hoch)/2 als Pivot-Datensatz, kann die Leistung der schnellen Sortierung im Worst-Case-Szenario erheblich verbessert werden. Wir können seine Leistung jedoch immer noch nicht im Fall von Array auf O (n) verbessern. Es gibt auch Möglichkeiten, die zeitliche Leistung des schnellen Sortierens im Worst-Case-Szenario in unterschiedlichem Maße zu verbessern.
Darüber hinaus erfordert die schnelle Sortierung einen rekursiven Stapel, der normalerweise nicht sehr tief ist und auf der Ebene der Protokoll (n) liegt. Wenn jedoch die Länge der beiden Arrays, die jeweils aufgeteilt sind, stark unausgeglichen ist, erhöht sich im schlimmsten Fall die Tiefe des Stapels auf O (n). Zu diesem Zeitpunkt kann die räumliche Komplexität, die der Stapelraum gebracht hat, nicht ignoriert werden. Wenn der Overhead zusätzlicher Variablen hinzugefügt wird, kann er hier sogar eine erschreckende o (n^2) Raumkomplexität erreichen. Daher ist die schlimmste räumliche Komplexität der schnellen Sortierung kein fester Wert und ist möglicherweise nicht einmal auf dem gleichen Niveau.
Um dieses Problem zu lösen, können wir die Längen der Enden nach jeder Teilung vergleichen und die kurzen Sequenzen zuerst sortieren (der Zweck ist es, diese Stapel zuerst zu beenden, um den Platz zu freien), was die maximale Tiefe auf die O (n) -Pegel zurücknehmen kann.
Hier sind drei Optimierungsideen zum schnellen Sortieren:
Für kleine Arrays kann die Sortierung von Einfügen verwendet werden, um rekursive Anrufe zu vermeiden. Wenn Sie beispielsweise (hi <= lo + m), können Sie zum Einfügen der Sortierung gehen.
Verwenden Sie den Median einer Subtarray, um das Array zu schneiden. Dies führt zu besserem Schneiden, aber zu Kosten für die Berechnung des Medianes.
Wenn das Array eine große Anzahl von Wiederholungselementen enthält, kann ein Drei-Wege-Schnitt verwendet werden. Teilen Sie das Array in drei Teile, was den Array -Elementen entspricht, die kleiner sind als, gleich und größer als das Schneiden von Elementen. Die Code -Implementierung ist wie folgt:
private static void sort1 (int [] a, int lo, int hi) {if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a [lo]; while (i <= gt) {if (a [i] <v) {swap (a, lt ++, i ++); } else if (a [i]> v) {swap (a, i, gt--); } else {i ++; } sort (a, lo, lt - 1); sortieren (a, gt + 1, hi); }}