Ein Algorithmus ist eine Reihe wohldefinierter Regeln, die zur Lösung eines Problems in einer begrenzten Anzahl von Schritten verwendet werden. Einfach ausgedrückt handelt es sich dabei um den Prozess, bei dem Computer Probleme lösen. Unabhängig davon, ob Sie in diesem Prozess eine Idee zur Problemlösung entwickeln oder ein Programm schreiben, implementieren Sie einen bestimmten Algorithmus. Ersteres ist ein Algorithmus, der durch Argumentation implementiert wird, und letzteres ist ein Algorithmus, der durch Operation implementiert wird.
Ein Algorithmus sollte die folgenden fünf wichtigen Eigenschaften aufweisen:
1. Endlichkeit: Ein Algorithmus muss sicherstellen, dass er nach der Ausführung einer endlichen Anzahl von Schritten endet;
2. Genauigkeit: Jeder Schritt des Algorithmus muss klar definiert sein;
3. Eingabe: Ein Algorithmus verfügt über 0 oder mehr Eingaben, um die Ausgangssituation des Operanden zu beschreiben;
4. Ausgabe: Ein Algorithmus verfügt über eine oder mehrere Ausgaben, die die Ergebnisse der Verarbeitung der Eingabedaten widerspiegeln. Ein Algorithmus ohne Ausgabe ist bedeutungslos;
5. Machbarkeit: Im Prinzip kann der Algorithmus präzise ausgeführt werden und von Personen ausgeführt werden, die Stift und Papier verwenden, um eine begrenzte Anzahl von Operationen durchzuführen.
Die Zusammenführungssortierung (MERGE SORT) ist eine andere Art verschiedener Sortiermethoden. Die Bedeutung der Zusammenführung besteht darin, zwei oder mehr geordnete Datensequenzen zu einer neuen geordneten Datensequenz zusammenzuführen. Daher wird sie auch als Zusammenführungsalgorithmus bezeichnet. Seine Grundidee besteht darin, anzunehmen, dass Array A N Elemente hat. Dann kann Array A als aus N geordneten Teilsequenzen bestehend betrachtet werden, wobei jede Teilsequenz eine Länge von 1 hat und dann zwei mal zwei zusammengeführt wird, um N/2 zu erhalten Eine geordnete Teilsequenz von Dann wird die Länge 2 oder 1 zu zweit zusammengeführt, und dies wird wiederholt, bis eine geordnete Datensequenz der Länge N erhalten wird. Diese Sortiermethode wird als 2-Wege-Zusammenführungssortierung bezeichnet.
Beispielsweise verfügt Array A über 7 Daten: 49 38 65 97 76 13 27. Der Vorgang der Verwendung des Zusammenführungssortierungsalgorithmus ist in Abbildung 7 dargestellt:
Anfangswert[49][38][65][97][76][13][27]
Wird als bestehend aus 7 Teilsequenzen der Länge 1 angesehen. Nach der ersten Fusion [38 49] [65 97] [13 76] [27]
Wird als aus 4 Teilsequenzen der Länge 1 oder 2 bestehend angesehen. Nach der zweiten Fusion [38 49 65 97] [13 27 76]
Wird als aus 2 Teilsequenzen der Länge 4 oder 3 bestehend angesehen. Nach der dritten Fusion [13 27 38 49 65 76 97]
Abbildung 6: Prozessdiagramm des Zusammenführungssortierungsalgorithmus. Die Kernoperation des Zusammenführungsalgorithmus besteht darin, zwei benachbarte geordnete Sequenzen in einem eindimensionalen Array zu einer geordneten Sequenz zusammenzuführen. Der Zusammenführungsalgorithmus kann auch mit einem rekursiven Algorithmus implementiert werden, der zwar eine relativ einfache Form hat, aber wenig praktisch ist.
Die Anzahl der Zusammenführungen im Zusammenführungsalgorithmus ist eine sehr wichtige Größe. Wenn das Array 3 bis 4 Elemente enthält, beträgt die Anzahl der Zusammenführungen 2, bei 5 bis 8 Elementen beträgt die Anzahl der Zusammenführungen 3 , und wenn es 9 bis 16 Elemente gibt, beträgt die Anzahl der Zusammenführungen 4. Nach dieser Regel kann bei N Teilsequenzen gefolgert werden, dass die Anzahl der Zusammenführungen beträgt
X (2>=N, das kleinste X, das die Unterbedingung erfüllt).
Beschreibung des Blasenalgorithmus:
Bevor wir den Blasensortierungsalgorithmus erklären, stellen wir zunächst einen Algorithmus vor, der die größte Zahl unter 10 Zahlen (in Array A) an der letzten Position einfügt. Der Algorithmus wird wie folgt beschrieben:
(1) Vergleichen Sie von Array A[1] bis A[10] zwei benachbarte Zahlen paarweise. Das heißt, A[1] wird mit A[2] verglichen, und nach dem Vergleich wird A[2] mit A[3] verglichen, ... und schließlich wird A[9] mit A[10] verglichen.
(2) Wenn bei jedem Vergleich die vorherige Zahl größer als die letztere Zahl ist, werden die beiden Zahlen vertauscht, d. h. die größere Zahl wird nach hinten und die kleinere Zahl nach vorne verschoben. Wenn beispielsweise im ersten Vergleich A[1] größer als A[2] ist, werden die Werte von A[1] und A[2] vertauscht. Die folgende Abbildung verwendet 6 Daten, um den obigen Algorithmus zu veranschaulichen.
Nehmen Sie an, dass die 6 Daten sind: A[]=5 7 4 3 8 6
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 Beim ersten Vergleich von A[1]=5 und A[2]=7, 7>5, wird kein Austausch durchgeführt.
5 7 4 3 8 6 Beim zweiten Mal werden A[2]=7 und A[3]=4 verglichen, 4<7, tauschen.
Dann sind die Daten nach dem zweiten Vergleich 5 4 7 3 8 6
5 4 7 3 8 6 Beim dritten Mal werden A[3]=7 und A[4]=3 verglichen, 3<7, tauschen.
Dann sind die Daten nach dem dritten Vergleich 5 4 3 7 8 6
5 4 3 7 8 6 Beim vierten Mal werden A[4]=7 und A[5]=8 verglichen, 8>7, es wird kein Austausch durchgeführt.
5 4 3 7 8 6 Beim fünften Mal werden A[6]=6 und A[5]=8 verglichen, 6<8, tauschen.
Dann ist das fünfte und letzte Ergebnis
5 4 3 7 6 8
************************************************** ******
Beschreibung des Auswahlsortierungsalgorithmus:
Bevor wir die Auswahlsortiermethode einführen, stellen wir einen Algorithmus vor, der die kleinste Zahl an die erste Stelle setzt. Natürlich können Sie auch die oben erwähnte Blasensortiermethode verwenden: Es gibt keine Eile Ändern Sie zunächst die Positionen. Um zu sehen, welche Zahl die kleinste ist, notieren Sie die Position P der Zahl. Nachdem der Scan abgeschlossen ist, tauschen Sie A[P] und A[1]. , dann werden die kleinsten Daten in A[1] bis A[10] an die vordere Position verschoben. Die Schritte des Algorithmus sind wie folgt:
1) Nehmen Sie zunächst an, dass die Zahl in A [1] die kleinste ist, und notieren Sie die Position P = 1 zu diesem Zeitpunkt.
2) Vergleichen Sie A[P] und A[I] nacheinander (I ändert sich von 2 auf 10, wenn die Zahl in A[I] kleiner ist als die Zahl in A[P], dann I Der Wert). wird P zugewiesen, sodass P immer auf die Position der kleinsten aktuell gescannten Zahl zeigt, d. h. A[P] ist immer gleich der kleinsten Zahl aller gescannten Zahlen. Nach dem Vergleich nacheinander zeigt P auf die Position der kleinsten Zahl unter den 10 Zahlen, dh A[P] ist die kleinste Zahl unter den 10 Zahlen;
3) Vertauschen Sie die Zahlen von A[P] und A[1], dann befindet sich die kleinste Zahl in A[1], also vorne.
Wenn Sie diesen Algorithmus nun wiederholen, wird der Bereich der zu vergleichenden Reihe bei jeder Wiederholung um eine Position nach hinten verschoben. Das heißt, im zweiten Vergleich reicht der Bereich von der 2. Zahl bis zur N-ten Zahl. Suchen Sie die Position P der kleinsten Zahl in diesem Bereich und vertauschen Sie dann A[P] und A[2], sodass ab der 2. Zahl Die kleinste Zahl vom Anfang bis zur N-ten Zahl ist in A[2]. Das dritte Mal besteht darin, die kleinste Zahl von der 3. Zahl bis zur N-ten Zahl zu finden und dann A[P] und A[3] einzufügen. Nachdem dieser Vorgang N-1 Mal wiederholt wurde, werden die N Zahlen im A-Array in der Reihenfolge von klein nach groß angeordnet. Diese Sortiermethode ist die Auswahlsortierung.
************************************************** ****************
Beschreibung des Einfügesortieralgorithmus:
Durch das Erlernen der beiden oben genannten Methoden können Sie die Grundidee des Sortierens verstehen und jedes ungeordnete Array von groß nach klein (absteigende Reihenfolge) oder von klein nach groß (aufsteigende Reihenfolge) anordnen. Nehmen wir nun an, dass es eine bereits geordnete Datensequenz gibt und es erforderlich ist, eine Zahl in diese bereits geordnete Datensequenz einzufügen, die Datensequenz muss jedoch nach dem Einfügen noch geordnet sein. Zu diesem Zeitpunkt wird eine neue Sortiermethode angewendet verwendet werden - Einfügungssortierungsmethode. Der grundlegende Vorgang der Einfügungssortierung besteht darin, Daten in die sortierten geordneten Daten einzufügen, um neue geordnete Daten mit der Zahl plus eins zu erhalten.
Frage: Es gibt N Daten in der Reihenfolge von klein nach groß. Geben Sie eine Zahl X ein und fügen Sie den Wert von X in Array A ein, sodass das eingefügte Array A weiterhin in der Reihenfolge von klein nach groß angeordnet ist .
Dann lautet der Algorithmus zur Lösung dieses Problems:
1) Finden Sie die Position, an der X eingefügt werden soll, indem Sie die Größe vergleichen, wenn es an der I-ten Position platziert werden soll;
2) Verschieben Sie alle Array-Elemente beginnend bei I (einschließlich I) um eine Position nach hinten, dh A[I+1]:=A[I];
Die Schnellsortierung ist eine Verbesserung gegenüber der Blasensortierung. Seine Grundidee besteht darin, die zu sortierenden Daten durch Einwegsortierung in zwei unabhängige Teile aufzuteilen. Alle Daten in einem Teil sind kleiner als alle Daten im anderen Teil, und dann werden die beiden Teile der Daten nacheinander sortiert. Für eine schnelle Sortierung kann der gesamte Sortiervorgang rekursiv durchgeführt werden, sodass die gesamten Daten zu einer geordneten Reihenfolge werden.
Angenommen, das zu sortierende Array ist A[1]...A[N]. Wählen Sie zunächst zufällig einen Datenwert (normalerweise den ersten Datenwert) als Schlüsseldaten aus und setzen Sie dann alle Zahlen, die größer sind, davor. und alle Zahlen, die größer als diese sind, werden dahinter platziert. Dieser Vorgang wird als schnelle Sortierung bezeichnet. Der Algorithmus für die schnelle Sortierung lautet:
1) Legen Sie zwei Variablen I und J fest. Wenn die Sortierung beginnt, I:=1, J:=N;
2) Verwenden Sie das erste Array-Element als Schlüsseldaten und weisen Sie es X zu, dh X:=A[1];
3) Suchen Sie vorwärts von J, das heißt, suchen Sie vorwärts von hinten (J:=J-1), finden Sie den ersten Wert, der kleiner als X ist, und tauschen Sie die beiden aus;
4) Suchen Sie von I aus rückwärts, dh von vorne nach hinten (I: = I + 1), finden Sie den ersten Wert, der größer als X ist, und tauschen Sie die beiden aus.
5) Wiederholen Sie die Schritte 3 und 4, bis I=J;
Beispiel: Die zu sortierenden Werte von Array A sind: (anfängliche Schlüsseldaten X:=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
Nach dem ersten Austausch: 27 38 65 97 76 13 49
(Nach der Suche von hinten gemäß dem dritten Schritt des Algorithmus für den zweiten Austausch: 27 38 49 97 76 13 65
(Folgen Sie dem vierten Schritt des Algorithmus und beginnen Sie von vorne, um den Wert > zu finden
Nach dem dritten Austausch: 27 38 13 97 76 49 65
(Gemäß dem fünften Schritt des Algorithmus wird der dritte Schritt des Algorithmus erneut vom Ende ausgeführt, um den vierten Austausch zu finden: 27 38 13 49 76 97 65
(Folgen Sie dem vierten Schritt des Algorithmus und beginnen Sie von vorne, um einen Wert größer als X, 97>49, zu finden, tauschen Sie die beiden aus, zu diesem Zeitpunkt J:=4)
Zu diesem Zeitpunkt wird bei der Ausführung des dritten Schritts festgestellt, dass I = J ist, wodurch die Schnellsortierung beendet wird. Das Ergebnis nach der Schnellsortierung ist: 27 38 13 49 76 97 65, das heißt, alle Zahlen größer als 49 sind in 49 , also stehen Zahlen unter 49 alle vor 49.
Die schnelle Sortierung besteht darin, diesen Prozess rekursiv aufzurufen. Teilen Sie die Datensequenz mit 49 als Mittelpunkt auf, führen Sie eine ähnliche schnelle Sortierung für den vorderen Teil bzw. den hinteren Teil durch, wodurch die schnelle Sortierung der gesamten Datensequenz abgeschlossen wird, und drehen Sie schließlich die Datensequenz um In eine geordnete Reihenfolge wird der gesamte Prozess der schnellen Sortierung des obigen Arrays A in Abbildung 6 dargestellt:
Ausgangszustand {49 38 65 97 76 13 27}
Nach einer kurzen Sortierung wird es in {27 38 13} 49 {76 97 65} unterteilt.
Vorder- und Hinterteil schnell sortieren {13} 27 {38}
Ende Ende {49 65} 76 {97} 49 {65} Ende Ende
************************************************** **************************
Abbildung 6 Algorithmusbeschreibung der Schnellsortierung während des gesamten Schnellsortierungsprozesses
1) Angenommen, N (unter der Annahme, dass N=10) Zahlen im S-Array gespeichert sind;
2), in S[1. . Nehmen Sie ein beliebiges Element in N] als Vergleichsbasis, beispielsweise T=S[1]. Der ursprüngliche Zweck besteht darin, die Position K zu bestimmen, an der sich T im Sortierergebnis befinden sollte. Die Position von K ist: S[1]. . . K-1]<=S[K]<=S[K+1..N], das heißt, die Zahlen vor S[K] sind alle kleiner als S[K] und die Zahlen nach S[K] sind es alle größer als S[ K];
3) Die Verwendung der Divide-and-Conquer-Idee (d. h. der Strategie, Groß und Klein klein zu machen) kann S[1 weiter verbessern. . K-1] und S[K+1. . N] Die beiden Datensätze werden dann schnell sortiert, bis nur noch ein Datenwert im Gruppierungsobjekt vorhanden ist.
Wenn die spezifischen Daten wie folgt lauten, lautet der erste schnelle Sortiervorgang:
Array-Index: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
ij
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53