Der Sortieralgorithmus wird an vielen Stellen verwendet. Ich habe den Algorithmus kürzlich noch einmal überprüft und ihn einfach selbst implementiert. Ich werde ihn hier aufzeichnen und etwas Material für eine zukünftige Überprüfung speichern.
Werfen wir ohne weitere Umschweife einen Blick nacheinander auf die klassischen Sortieralgorithmen:
1. Wählen Sie Sortieren
Die Grundidee der Auswahlsortierung besteht darin, dass Sie beim Durchlaufen des Arrays, wenn i die aktuelle Sequenznummer darstellt, die sortiert werden muss, den Mindestwert unter den verbleibenden [i...n-1] finden müssen. , und zeigen Sie dann den gefundenen Minimalwert an, um i-Werte auszutauschen. Da jeder Prozess zum Bestimmen von Elementen einen Unterprozess zum Auswählen des Maximalwerts hat, wird dies im Volksmund auch als Auswahlsortierung bezeichnet. Nehmen wir ein Beispiel:
Initiale: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2, 17, 16, 16, 7, 31, 39, 32, 38, 11] (0. [38]<->8. [2])
i = 1: [2, 7, 16, 16, 17, 31, 39, 32, 38, 11] (1. [38]<->4. [17])
i = 2: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (2. [11]<->9. [16])
i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (kein Austausch erforderlich)
i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4. [17]<->9. [16])
i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5. [31]<->9. [17])
i = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6. [39]<->9. [31])
i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (kein Austausch erforderlich)
i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (kein Austausch erforderlich)
i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (kein Austausch erforderlich)
Wie aus dem Beispiel ersichtlich ist, wird die Anzahl der Vergleiche mit fortschreitender Auswahlsortierung (i allmählich zunehmend) immer geringer. Unabhängig davon, ob das Array anfänglich geordnet ist oder nicht, führt die Auswahlsortierung jedoch einen Auswahlvergleich durch Von i bis zum Ende des Arrays ist die Anzahl der Vergleiche bei der Auswahlsortierung also festgelegt: 1 + 2 + 3 + … + n = n * (n + 1) / 2 , und die Anzahl der Austausche hängt von der Reihenfolge des anfänglichen Arrays ab. Wenn die anfängliche Array-Reihenfolge zufällig ist, werden die Array-Elemente im schlimmsten Fall n-mal ausgetauscht, und im besten Fall kann es 0-mal sein ( das Array selbst ist eine Sequenz).
Daraus lässt sich ableiten, dass die zeitliche Komplexität und die räumliche Komplexität der Auswahlsortierung O(n2) bzw. O(1) sind (die Auswahlsortierung erfordert nur zusätzlichen Platz für den Austausch von Array-Elementen).
Implementierungscode:
Kopieren Sie den Codecode wie folgt:
/**
*Auswahlsortierung
*/
SELECTION(new Sortable() {
public <T erweitert Comparable<T>> void sort(T[] array, boolean aufsteigend) {
int len = array.length;
for (int i = 0; i < len; i++) {
int selected = i;
for (int j = i + 1; j < len; j++) {
int vergleichen = array[j].compareTo(array[selected]);
if (vergleiche != 0 && vergleiche < 0 == aufsteigend) {
ausgewählt = j;
}
}
Exchange(Array, i, selected);
}
}
})
2. Einfügungssortierung
Die Grundidee der Einfügungssortierung besteht darin, dass beim Durchlaufen des Arrays unter der Annahme, dass die Elemente vor der Seriennummer i, also [0..i-1], sortiert wurden, diese Reise die richtige Position finden muss k des Elements x, das i entspricht, und beim Finden dieser Position k werden die verglichenen Elemente nacheinander um eine Position nach hinten verschoben, um „Platz“ für Element x zu schaffen. Schließlich wird der Elementwert zugewiesen, der k entspricht x. Die Einfügungssortierung wird auch nach den Sortiermerkmalen benannt.
Das Folgende ist ein Beispiel. Die durchgestrichenen Zahlen sind Elemente, die an dieser Sortierung nicht beteiligt sind. Die Elemente zwischen den rot markierten Zahlen und den durchgestrichenen Zahlen sind Elemente, die nach hinten verschoben sind Eins nach dem anderen, z. B. Die an der zweiten Sortierung beteiligten Elemente sind [11, 31, 12], und das einzufügende Element ist 12, aber 12 befindet sich derzeit nicht an der richtigen Position, daher müssen wir es mit einfügen die vorherigen Elemente 31 und 11 der Reihe nach. Vergleichen Sie, verschieben Sie die verglichenen Elemente während des Vergleichs und beenden Sie den Vergleich, wenn Sie das erste Element 11 finden, das kleiner als 12 ist. Zu diesem Zeitpunkt ist der Index 1, der 31 entspricht, die Position, an der 12 eingefügt werden muss.
Anfänglich: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
Erster Durchgang: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (keine verschobenen Elemente)
Zweite Fahrt: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 bewegt sich rückwärts)
Dritte Fahrt: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 bewegen sich alle rückwärts)
Vierter Durchgang: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (keine beweglichen Elemente)
Fünfte Fahrt: [5, 11, 12, 30, 31, 34, 26, 38, 36, 18] (31, 34 bewegt sich rückwärts)
Die sechste Fahrt: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31, 34 bewegt sich rückwärts)
Der siebte Durchgang: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (keine beweglichen Elemente)
Achter Trip: [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 bewegt sich rückwärts)
Neunte Fahrt: [5, 11, 12, 18, 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 rückwärts)
Die Einfügungssortierung ist besser als die Auswahlsortierung, da sie die Tatsache ausnutzen kann, dass der erste Teil der Array-Elemente während des Sortiervorgangs sortiert wurde, wodurch die Anzahl der Vergleiche effektiv reduziert wird. Dieser Vorteil hängt natürlich von der anfänglichen Reihenfolge ab Array. Im schlechten Fall (das angegebene Array ist zufällig in umgekehrter Reihenfolge) ist die Anzahl der für die Einfügungssortierung erforderlichen Vergleiche und Verschiebungen gleich 1 + 2 + 3... + n = n * (n + 1) / 2. In diesem Extremfall ist die Effizienz der Einfügungssortierung noch schlechter als die der Auswahlsortierung. Daher ist die Einfügungssortierung eine instabile Sortiermethode, und die Einfügungseffizienz hängt eng mit der ursprünglichen Reihenfolge des Arrays zusammen. Im Allgemeinen betragen die zeitliche Komplexität und die räumliche Komplexität der Einfügungssortierung O(n2) bzw. O(1).
Implementierungscode:
Kopieren Sie den Codecode wie folgt:
/**
*Einfügesortierung
*/
INSERTION(new Sortable() {
public <T erweitert Comparable<T>> void sort(T[] array, boolean aufsteigend) {
int len = array.length;
for (int i = 1; i < len; i++) {
T toInsert = array[i];
int j = i;
für (; j > 0; j) {
int vergleichen = array[j - 1].compareTo(toInsert);
if (vergleiche == 0 || vergleiche < 0 == aufsteigend) {
brechen;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
}
})
3. Blasensortierung
Die Blasensortierung kann als der klassischste Sortieralgorithmus angesehen werden. Ich erinnere mich, dass dieser Algorithmus der erste war, mit dem ich in der Schule in Kontakt kam. Da die Implementierungsmethode die einfachste ist, handelt es sich um eine zweistufige for-Schleife In der inneren Schleife wird beurteilt, ob zwei benachbarte Elemente in umgekehrter Reihenfolge vorliegen. Wenn ja, werden die beiden Elemente ausgetauscht und eine äußere Schleife ausgeführt, um das kleinste Element unter den verbleibenden Elementen im Array nach vorne zu „schweben“, so heißt es Blasensortierung.
Geben wir wie üblich ein einfaches Beispiel:
Ausgangszustand: [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
Die erste Fahrt der inneren Schicht: [24, 19, 26, 39, 36, 7, 31, 29, 23, 38] (9. [23]<->8. [38)
Zweiter Durchgang der inneren Schicht: [24, 19, 26, 39, 36, 7, 31, 23, 29, 38] (8. [23]<->7. [29])
Der dritte Durchgang der inneren Schicht: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7. [23] <-> 6. [31])
Der vierte Durchgang der inneren Schicht: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7 und 23 sind alle in der richtigen Reihenfolge, kein Austausch erforderlich)
Die fünfte Reise der inneren Schicht: [24, 19, 26, 39, 7, 36, 23, 31, 29, 38] (5. [7] <-> 4. [36])
Die sechste Reise der inneren Schicht: [24, 19, 26, 7, 39, 36, 23, 31, 29, 38] (4. [7] <-> 3. [39])
Der siebte Durchgang der inneren Schicht: [24, 19, 7, 26, 39, 36, 23, 31, 29, 38] (3. [7] <-> 2. [26])
Der achte Durchgang der inneren Schicht: [24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (2. [7]<->1. [19])
Die neunte Reise der inneren Schicht: [7, 24, 19, 26, 39, 36, 23, 31, 29, 38] (1. [7]<->0. [24])
……….
Tatsächlich ähnelt die Blasensortierung der Auswahlsortierung. Die Anzahl der Vergleiche ist gleich, n * (n + 1) / 2. Die Blasensortierung führt jedoch zusätzliche Austausche bei der Auswahl des Mindestwerts durch (die Blasensortierung ist nur erforderlich). Wenn festgestellt wird, dass die Reihenfolge benachbarter Elemente nicht korrekt ist, wird die Auswahlsortierung erst nach Abschluss des Innenschleifenvergleichs über den Austausch entscheiden. Meiner Meinung nach gehört die Auswahlsortierung dazu zur Blasensortierung.
Implementierungscode:
Kopieren Sie den Codecode wie folgt:
/**
* Blasensortierung, es ist der Einfügungssortierung sehr ähnlich
*/
BUBBLE(new Sortable() {
public <T erweitert Comparable<T>> void sort(T[] array, boolean aufsteigend) {
int length = array.length;
int lastExchangedIdx = 0;
for (int i = 0; i < length; i++) {
// Markieren Sie das Flag zur Identität, ob der Austausch mit „false“ erfolgt ist
boolean isExchanged = false;
// Der letzte Vergleich und Austausch fand statt, bevor Index i erreicht wurde
int currOrderedIdx = lastExchangedIdx > i ? lastExchangeIdx : i;
for (int j = length 1; j > currOrderedIdx; j) {
int vergleichen = array[j - 1].compareTo(array[j]);
if (vergleiche != 0 && vergleiche > 0 == aufsteigend) {
Austausch(Array, j 1, j);
isExchanged = true;
lastExchangeIdx = j;
}
}
// Wenn kein Austausch stattfindet, bedeutet das, dass das Array bereits in Ordnung ist
if (isExchanged == false) {
brechen;
}
}
}
})
4. Hügelsortierung
Die Hill-Sortierung wurde geboren, weil die Einfügungssortierung beim Umgang mit großen Arrays auf das Problem stieß, zu viele Elemente zu verschieben. Die Idee der Hill-Sortierung besteht darin, ein großes Array in mehrere kleine Arrays zu „teilen und zu erobern“, die durch Lücken unterteilt sind, z. B. das Array [1, 2, 3, 4, 5, 6, 7, 8]. = 2 zu teilen, kann in zwei Arrays [1, 3, 5, 7] und [2, 4, 6, 8] unterteilt werden (entsprechend, z. B. Lücke = 3). , dann sind die geteilten Arrays: [1, 4, 7], [2, 5, 8], [3, 6]) Führen Sie dann eine Einfügungssortierung für die geteilten Arrays durch und reduzieren Sie sie dann, nachdem jedes Unterarray sortiert wurde. Wiederholen Sie die vorherigen Schritte, bis Lücke = 1 Das heißt, die Einfügungssortierung wird für das gesamte Array durchgeführt. Zu diesem Zeitpunkt ist das Array grundsätzlich sortiert, sodass die Elemente, die verschoben werden müssen, sehr klein sind, wodurch das Problem gelöst wird, dass bei der Einfügungssortierung mehr Verschiebungen auftreten, wenn große Mengen verarbeitet werden. Skalierungsarrays.
Spezifische Beispiele finden Sie unter Einfügungssortierung.
Die Hill-Sortierung ist eine verbesserte Version der Einfügungssortierung. Sie ist sehr hilfreich, um die Effizienz zu verbessern, wenn die Datenmenge klein ist. Es wird empfohlen, die Einfügungssortierung direkt zu verwenden.
Implementierungscode:
Kopieren Sie den Codecode wie folgt:
/**
* Muschelsortierung
*/
SHELL(new Sortable() {
public <T erweitert Comparable<T>> void sort(T[] array, boolean aufsteigend) {
int length = array.length;
int Lücke = 1;
// Verwenden Sie die nächste Lücke zur Länge / 3 als erste Lücke
while (Lücke < Länge / 3) {
Lücke = Lücke * 3 + 1;
}
while (Lücke >= 1) {
for (int i = Lücke; i < Länge; i++) {
T next = array[i];
int j = i;
while (j >= Lücke) {
int vergleichen = array[j - Lücke].compareTo(next);
// Finde bereits seine Position
if (vergleiche == 0 || vergleiche < 0 == aufsteigend) {
brechen;
}
array[j] = array[j - Lücke];
j -= Lücke;
}
if (j != i) {
array[j] = next;
}
}
Lücke /= 3;
}
}
})
5. Sortierung zusammenführen
Die Zusammenführungssortierung wird durch Rekursion implementiert, bei der es sich um eine „Teile-und-Herrsche“-Methode handelt. Das Zielarray wird von der Mitte aus in zwei Teile geteilt, und dann werden die beiden Arrays getrennt sortiert. Nach Abschluss der Sortierung werden die beiden sortierten Arrays „zusammengeführt“. " In Together ist das Wichtigste bei der Zusammenführungssortierung der Prozess des Zusammenführens. Der Zusammenführungsprozess erfordert zusätzlichen Speicherplatz, der mit der Länge der beiden Arrays übereinstimmt, die zusammengeführt werden müssen. Beispielsweise die Arrays, die angegeben werden müssen sind: [3, 6, 8, 11] und [1, 3, 12, 15] (Obwohl diese Elemente logisch in zwei Arrays unterteilt sind, befinden sie sich tatsächlich noch im ursprünglichen Array, sind jedoch durch einige Indizes in zwei Arrays unterteilt. Das ursprüngliche Array Für [3, 6, 8, 11, 1, 3, 12, 15, wir setzen drei Zeiger lo, mid und high auf 0, 3 bzw. 7. Eine logische Teilarray-Aufteilung kann erreicht werden. Dann beträgt die Länge des zusätzlich benötigten Arrays 4 + 4 = 8. Der Zusammenführungsprozess lässt sich kurz wie folgt zusammenfassen:
1) Kopieren Sie die Elemente in den beiden Unterarrays in das neue Array copyArray. Nehmen Sie das oben genannte Beispiel als Beispiel: copyArray = [3, 6, 8, 11, 1, 3, 12, 15];
2) Setzen Sie zwei Zeiger so, dass sie jeweils auf das entsprechende erste Element im atomaren Array zeigen. Angenommen, die beiden Zeiger heißen leftIdx und rightIdx, dann ist leftIdx = 0 (entsprechend dem ersten Element [3] im kopierten Array), rightIdx = 4 ( entsprechend dem fünften Element [1] in copyArray);
3) Vergleichen Sie die Werte der Array-Elemente, auf die leftIdx und rightIdx zeigen, wählen Sie das kleinere aus und weisen Sie seinen Wert der entsprechenden Position i im ursprünglichen Array zu. Führen Sie nach Abschluss der Zuweisung eine automatische Inkrementierungsoperation für aus Wenn der Wert leftIdx oder rigthIdx das Ende des entsprechenden Arrays erreicht hat, müssen nur noch die verbleibenden Array-Elemente der Reihe nach an die verbleibenden Positionen kopiert werden.
Hier ist ein konkretes Beispiel für die Zusammenführung:
Erste Reise:
Hilfsarray [21, 28, 39 | 35, 38] (das Array ist in zwei linke und rechte Unterarrays aufgeteilt, getrennt durch |)
[21, , , , ] (Beim ersten Vergleich von 21 mit 35 gewinnt das linke Subarray, leftIdx = 0, i = 0)
Zweite Reise:
Hilfsarray [21, 28, 39 |.
[21, 28, , , ] (Beim zweiten Vergleich von 28 mit 35 gewinnt das linke Subarray, leftIdx = 1, i = 1)
Dritte Reise: [21, 28, 39 |.
[21, 28, 35, , ] (Beim dritten Vergleich von 39 mit 35 gewinnt das rechte Subarray, rightIdx = 0, i = 2)
Die vierte Reise: [21, 28, 39 |.
[21, 28, 35, 38,] (Beim vierten Vergleich von 39 und 38 gewinnt das rechte Subarray, rightIdx = 1, i = 3)
Die fünfte Reise: [21, 28, 39 |.
[21, 28, 35, 38, 39] (Das rechte Unterarray wurde zum fünften Mal kopiert, kein Vergleich erforderlich, leftIdx = 2, i = 4)
Das Obige ist ein Zusammenführungsprozess. Wir können das gesamte Array, das sortiert werden muss, eine begrenzte Anzahl von Malen aufteilen (jedes Mal in zwei Teile aufteilen), bis es in ein kleines Array mit einer Länge von 1 unterteilt ist. Wenn die Länge 1 beträgt, Das Array muss nicht mehr sortiert werden. Danach werden diese Arrays in umgekehrter Reihenfolge zusammengeführt (aufgrund der Rekursion), bis das letzte Unterarray der Länge n/2 zusammengeführt ist. Nach Abschluss der Zusammenführung ist auch die Array-Sortierung abgeschlossen.
Die Zusammenführungssortierung erfordert den größten zusätzlichen Platz aller Sortierungen, und jede Zusammenführung erfordert die gleiche Anzahl von Elementen wie die Summe der Längen der beiden an der Zusammenführung beteiligten Arrays (um ein Hilfsarray bereitzustellen). Daraus lässt sich schließen, dass die räumliche Komplexität der Zusammenführungssortierung 1 + 2 + 4 + ... + n = n * (n + 2) / 4 beträgt (ohne Berücksichtigung der Paritätsbeurteilung von n). Die zeitliche Komplexität ist schwer abzuschätzen . Hier habe ich auch vergessen, wie viele ().
Implementierungscode:
Kopieren Sie den Codecode wie folgt:
/**
* Sortierung zusammenführen
*/
MERGE(new Sortable() {
public <T erweitert Comparable<T>> void sort(T[] array, boolean aufsteigend) {
this.sort(array, 0, array.length 1, aufsteigend);
}
private <T erweitert Comparable<T>> void sort(T[] array, int lo, int hi, boolean aufsteigend) {
// EINES OPTIMIEREN
// wenn die Länge des Teilstrings weniger als 20 beträgt,
// Einfügungssortierung verwenden, um rekursive Aufrufe zu reduzieren
if (hi lo < 20) {
for (int i = lo + 1; i <= hi; i++) {
T toInsert = array[i];
int j = i;
für (; j > lo; j) {
int vergleichen = array[j - 1].compareTo(toInsert);
if (vergleiche == 0 || vergleiche < 0 == aufsteigend) {
brechen;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
zurückkehren;
}
int mid = lo + (hi lo) / 2;
sort(array, lo, mid, aufsteigend);
sort(array, mid + 1, hi, aufsteigend);
merge(array, lo, mid, hi, aufsteigend);
}
private <T erweitert Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean aufsteigend) {
// ZWEI OPTIMIEREN
// Wenn es bereits in der richtigen Reihenfolge ist, überspringen Sie diese Zusammenführung
// da es keine Notwendigkeit gibt, dies zu tun
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == aufsteigend) {
zurückkehren;
}
@SuppressWarnings("ungeprüft")
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0;
int highIdx = mid lo + 1;
for (int i = lo; i <= hi; i++) {
if (lowIdx > mid lo) {
// linkes Unterarray erschöpft
array[i] = arrayCopy[highIdx++];
} else if (highIdx > hi lo) {
// rechtes Unterarray erschöpft
array[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == aufsteigend) {
array[i] = arrayCopy[lowIdx++];
} anders {
array[i] = arrayCopy[highIdx++];
}
}
}
})
6. Schnelle Sortierung
Die Schnellsortierung ist ebenfalls ein „Teile-und-Herrsche“-Sortieralgorithmus, der mithilfe der Zusammenführungsmethode implementiert wird. Sein Charme besteht darin, dass er die endgültige korrekte Position der Sortierung für ein Array-Element in jeder Partition (dem Kern des Sortieralgorithmus) (einmal) bestimmen kann Bei korrekter Positionierung wird dieses Element im nächsten Zyklus nicht berücksichtigt.