Blasensortierungsalgorithmus

Die Grundidee der Austauschsortierung besteht darin, die Schlüsselwörter der zu sortierenden Datensätze paarweise zu vergleichen. Wenn festgestellt wird, dass die Reihenfolge der beiden Datensätze umgekehrt ist, wird der Austausch durchgeführt, bis Es gibt keine Datensätze in umgekehrter Reihenfolge.

Die wichtigsten Sortiermethoden, die die Grundidee der Austauschsortierung anwenden, sind: Blasensortierung und Schnellsortierung.

Blasensortierung

1. Sortiermethode
Ordnen Sie das sortierte Datensatzarray R[1..n] vertikal an, und jeder Datensatz R[i] hat ein Gewicht von Blasen für R[i].key. Gemäß dem Prinzip, dass sich leichte Blasen nicht unter schweren Blasen befinden können, wird das Array R von unten nach oben gescannt: Jede leichte Blase, die gegen dieses Prinzip verstößt, wird nach oben „schweben“. Dies wird wiederholt, bis die letzten beiden Blasen die leichtere oben und die schwerere unten sind.
(1) Das anfängliche
R[1..n] ist ein ungeordneter Bereich.

(2) Der erste Scan
Vergleichen Sie die Gewichte zweier benachbarter Blasen vom Boden des ungeordneten Bereichs aufwärts. Wenn festgestellt wird, dass sich die leichtere Blase unten und die schwerere Blase befindet oben, vertauschen Sie die Positionen der beiden. Das heißt, vergleichen Sie (R[n], R[n-1]), (R[n-1], R[n-2]),..., (R[2], R[1]) in Sequenz; für jedes Paar Blase (R[j+1], R[j]), wenn R[j+1].key Wenn der erste Scan abgeschlossen ist, schwebt die „leichteste“ Blase an die Spitze des Intervalls, d. h. der Datensatz mit dem kleinsten Schlüsselwort wird an der höchsten Position R[1] platziert.

(3) Der zweite Scan
Scan R[2..n]. Wenn der Scan abgeschlossen ist, schwebt die Blase des „zweiten Lichts“ an die Position von R[2]...
Schließlich kann nach n-1 Scans der geordnete Bereich R[1..n]
sein Hinweis:
Während des i-ten Scans sind R[1..i-1] und R[i..n] der aktuelle geordnete Bereich bzw. der ungeordnete Bereich. Das Scannen erfolgt immer noch vom unteren Ende des ungeordneten Bereichs nach oben zum oberen Ende des Bereichs. Wenn der Scan abgeschlossen ist, schwebt die leichteste Blase im Bereich zur obersten Position R[i], und das Ergebnis ist, dass R[1..i] zu einem neuen geordneten Bereich wird.

2. Beispiel für den Blasensortierungsprozess
Der Prozess der Blasensortierung einer Datei mit der Schlüsselwortsequenz 49 38 65 97 76 13 27 49

3. Sortieralgorithmus
(1 ) Analyse
Da bei jedem Sortiervorgang dem geordneten Bereich eine Blase hinzugefügt wird, sind nach n-1 Sortiervorgängen n-1 Blasen im geordneten Bereich vorhanden, während die Anzahl der Blasen im ungeordneten Bereich gleich ist immer größer oder gleich dem Gewicht der Blasen im geordneten Bereich, sodass der gesamte Blasensortierungsprozess höchstens n-1 Sortiervorgänge erfordert.
Wenn in einem bestimmten Sortierdurchgang kein Austausch der Blasenpositionen festgestellt wird, bedeutet dies, dass alle Blasen im ungeordneten Bereich, die sortiert werden sollen, dem Prinzip der leichteren oben und der schwereren unten genügen Der Blasensortiervorgang kann hier nach dem Sortieren beendet werden. Zu diesem Zweck wird im unten angegebenen Algorithmus ein boolescher Austausch eingeführt, der vor Beginn jeder Sortierung auf FALSE gesetzt wird. Wird auf TRUE gesetzt, wenn beim Sortieren ein Austausch stattfindet. Der Austausch wird am Ende jedes Sortierdurchlaufs überprüft. Wenn kein Austausch stattgefunden hat, wird der Algorithmus beendet und der nächste Sortierdurchlauf nicht durchgeführt.

(2) Spezifischer Algorithmus
void BubbleSort(SeqList R)
{ //R (l..n) ist die zu sortierende Datei, scannt von unten nach oben und sortiert nach Blase R
int i, j;
Boolean Exchange; //Exchange Flag
for(i=1;iexchange=FALSE ; /Bevor diese Sortierung beginnt, sollte das Austauschflag falsch sein
for(j=n-1;j>=i;j--) //Für den aktuellen ungeordneten Bereich R[i..n] vom unteren Scan up
if(R[j+1].key R[0]=R[j+1] //R[0] ist nicht Sentinel, nur eine temporäre Speichereinheit
R[j+1]=R[j];
R[j]=R[0];
Exchange=TRUE; //Es hat also ein Austausch stattgefunden the Das Austauschflag wird auf true gesetzt
}
if(!exchange) //Bei dieser Sortierung findet kein Austausch statt, Algorithmus vorzeitig beenden
/BubbleSort

Weitere Artikel zum Blasensortierungsalgorithmus finden Sie auf der chinesischen PHP-Website!