Quicksort wird häufig verwendet, weil seine Sortiereffizienz unter mehreren Sortierverfahren, die alle O(N*logN) sind, relativ hoch ist. Darüber hinaus ist die Idee des Quicksorts – die Divide-and-Conquer-Methode – tatsächlich praktisch. Daher testen viele Softwareunternehmen dies gern in schriftlichen Tests und Vorstellungsgesprächen, einschließlich bekannter IT-Unternehmen wie Tencent und Microsoft. Außerdem erscheint Quicksort häufig in programmierbezogenen Prüfungen verschiedener Größenordnungen, wie der Software-Qualifikationsprüfung und der Aufnahmeprüfung für das postgraduale Studium.

=a

Quicksort ist ein von C.R.A.Hoare im Jahr 1962 vorgeschlagenes Partition-Exchange-Sortierverfahren. Es verwendet eine Divide-and-Conquer-Strategie, die gewöhnlich Divide-and-Conquer-Methode genannt wird (Divide-and-Conquer Method).

Die Grundidee dieser Methode ist:

• 1. Zuerst nimmt man eine Zahl aus der Folge als Pivot.
• 2. Im Partitionierungsprozess werden alle Zahlen, die größer als diese Zahl sind, rechts von ihr platziert, und alle Zahlen, die kleiner oder gleich ihr sind, links von ihr.
• 3. Wiederholen Sie Schritt 2 für die linken und rechten Intervalle, bis jedes Intervall nur noch eine Zahl enthält.

Obwohl Quicksort als Divide-and-Conquer-Methode bezeichnet wird, können diese drei Wörter offensichtlich nicht alle Schritte des Quicksorts vollständig zusammenfassen. Daher habe ich eine weiterführende Erklärung des Quicksorts bereitgestellt: Löcher graben und Zahlen einsetzen + Divide-and-Conquer.

Schauen wir uns zunächst ein Beispiel an. Die Definition ist unten angegeben (am besten fasst man die Definition in eigenen Worten zusammen, da dies bei der Implementierung des Codes hilft).

 

Nimm ein Array als Beispiel und nimm die erste Zahl im Intervall als Pivot.

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

Anfangs ist i = 0; j = 9; X = a[i] = 72

Da die Zahl in a

Suche von j aus nach links nach einer Zahl, die kleiner oder gleich X ist. Wenn j=8, ist die Bedingung erfüllt. Grabe a aus

 

Das Array wird zu:

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

 

i = 3;   j = 7;   X=72

Wiederhole die obigen Schritte: Suche zuerst von hinten nach vorne, dann von vorne nach hinten.

Suche von j aus nach links. Wenn j=5, ist die Bedingung erfüllt. Grabe a aus

Suche von i aus nach rechts. Wenn i=5, brich ab, weil i==j.

An diesem Punkt ist i = j = 5, und a

Das Array wird zu:

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

Man erkennt, dass die Zahlen vor a

 

Fassen wir das Ausheben von Gruben und das Auffüllen von Zahlen zusammen:

• 1. i = L; j = R; hole das Pivot heraus, um das erste Loch a[i] zu bilden.
• 2. j--, suche von hinten nach vorne nach einer Zahl, die kleiner als das Pivot ist. Wenn du sie gefunden hast, nimm diese Zahl heraus und fülle sie in das vorherige Loch a[i] ein.
• 3. i++, suche von vorne nach hinten nach einer Zahl, die größer als das Pivot ist. Wenn du sie gefunden hast, nimm auch diese Zahl heraus und fülle sie in das vorherige Loch a[j] ein.
• 4. Wiederhole die Schritte 2 und 3, bis i==j gilt, und fülle dann das Pivot in a[i] ein.

Nach dieser Zusammenfassung ist es einfach, den Code für das Graben von Löchern und das Einfüllen von Zahlen zu implementieren:

int AdjustArray(int s[], int l, int r) //Gibt die Position des angepassten Pivots zurück { int i = l, j = r; int x = s[l]; //s[l], das heißt s[i], ist das erste Loch while (i < j) { // Suche von rechts nach links eine Zahl kleiner als x, um s[i] zu füllen while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; //Fülle s[j] in s[i] ein, dann bildet s[j] ein neues Loch i++; } // Suche von links nach rechts eine Zahl größer oder gleich x, um s[j] zu füllen while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; //Fülle s[i] in s[j] ein, dann bildet s[i] ein neues Loch j--; } } //Beim Verlassen ist i gleich j. Fülle x in dieses Loch ein. s[i] = x; return i; }

Schreibe dann den Code für die Divide-and-Conquer-Methode:

void quick_sort1(int s[], int l, int r) { if (l < r) { int i = AdjustArray(s, l, r);//Verwende zuerst die Methode des Lochgrabens und Zahlenauffüllens, um s[] anzupassen quick_sort1(s, l, i - 1); // Rekursiver Aufruf quick_sort1(s, i + 1, r); } }

Solcher Code ist offensichtlich nicht prägnant genug, also fasse ihn zusammen und räume ihn auf:

//Schnellsortierung void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); // Tausche die mittlere Zahl mit der ersten Zahl. Siehe Hinweis 1 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) //Finde die erste Zahl kleiner als x von rechts nach links j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) //Finde die erste Zahl größer oder gleich x von links nach rechts i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // Rekursiver Aufruf quick_sort(s, i + 1, r); } }

Es gibt viele verbesserte Versionen von Quicksort, z. B. die zufällige Auswahl des Pivots oder die direkte Verwendung einer anderen Sortiermethode, wenn weniger Daten im Intervall vorhanden sind, um die Rekursionstiefe zu reduzieren. Interessierte Freunde können dies weiter untersuchen.

Hinweis 1: Einige Bücher verwenden die mittlere Zahl als Pivot. Um dies umzusetzen, ist es sehr einfach – tauschen Sie einfach die mittlere Zahl mit der ersten Zahl.

Autor: MoreWindows

Originalartikel: https://blog.csdn.net/morewindows/article/details/6684558