Shells Sortierung ist ein sehr „magischer“ Sortieralgorithmus. Es wird „magisch“ genannt, weil niemand seine Leistung klar erklären kann. Hügelsortierung wegen DL. Shell wurde nach seinem Vorschlag im Jahr 1959 benannt. Seit C. A. R. Hoare 1962 die schnelle Sortierung vorschlug, wird die schnelle Sortierung im Allgemeinen verwendet, da sie einfacher ist. Viele Mathematiker arbeiten jedoch immer noch unermüdlich daran, die optimale Komplexität der Hill-Sortierung zu finden. Als normale Programmierer können wir aus Hills Ideen lernen.
Übrigens gab es vor dem Aufkommen der Hill-Sortierung in der Computerindustrie die allgemeine Ansicht, dass „Sortieralgorithmen O(n2) nicht durchbrechen können“. Das Aufkommen der Hill-Sortierung brach diesen Fluch und bald kamen Algorithmen wie die schnelle Sortierung nacheinander auf den Markt. In diesem Sinne führt uns Hill Sorting in eine neue Ära.
Algorithmusübersicht/Ideen
Der Vorschlag der Hill-Sortierung basiert hauptsächlich auf den folgenden zwei Punkten:
1 Wenn das Array grundsätzlich geordnet ist, kann der Einfügungssortierungsalgorithmus ungefähr O(n) erreichen. Komplexitätsgrad, äußerst effizient.
2. Bei der Einfügungssortierung können die Daten jedoch jeweils nur um ein Bit verschoben werden, und die Leistung nimmt schnell ab, wenn das Array groß und grundsätzlich ungeordnet ist.
Auf dieser Grundlage können wir eine gruppierte Einfügungssortiermethode verwenden. Die spezifische Methode ist: (Nehmen Sie ein Array mit 16 Elementen)
1. Wählen Sie das Subarray aus dem Array entsprechend dieser Schrittweite für eine Direkteinfügungssortierung aus. Wenn die ausgewählte Schrittweite beispielsweise 5 beträgt, werden die Elemente mit den Indizes 0, 5, 10 und 15 sortiert.
2. Behalten Sie das inkrementelle Delta bei und verschieben Sie das erste Element der Reihe nach für die Direkteinfügungssortierung, bis eine Runde abgeschlossen ist. Für das obige Beispiel werden die Arrays [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] der Reihe nach sortiert.
3. Reduzieren Sie das Inkrement und wiederholen Sie den obigen Vorgang, bis das Inkrement auf 1 reduziert ist. Das letzte Mal ist natürlich die direkte Einfügungssortierung.
4. Sortierung abgeschlossen.
Wie aus dem Obigen ersichtlich ist, nimmt das Inkrement ständig ab, daher wird die Hill-Sortierung auch als „Sortierung mit schrumpfendem Inkrement“ bezeichnet.
Code-Implementierung
package sort;
public class ShellSortTest {
public static int count = 0;
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
shellSort(data);
print(data);
}
public static void shellSort(int[] data) {
// 计算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (int i = h; i < data.length; i += h) {
if (data[i] < data[i - h]) {
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
print(data);
}
}
// 计算出下一个h值
h = (h - 1) / 3;
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}Nach dem Login kopieren
Ausführungsergebnisse:
5 3 6 2 1 9 4 8 7
1 3 6 2 5 9 4 8 7
1 2 3 6 5 9 4 8 7
1 2 3 5 6 9 4 8 7
1 2 3 4 5 6 9 8 7
1 2 3 4 5 6 8 9 7
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
Nach dem Login kopieren
Algorithmusleistung/-komplexität
Die inkrementelle Reihenfolge der Hill-Sortierung kann nach Bedarf ausgewählt werden Bedingung ist, dass die letzte Zahl 1 sein muss (da sie nach 1 geordnet sein muss). Allerdings haben unterschiedliche Sequenzauswahlen einen großen Einfluss auf die Leistung des Algorithmus. Der obige Code zeigt zwei Inkremente.
Denken Sie daran: Es ist am besten, keinen anderen gemeinsamen Faktor als 1 für alle zwei Elemente in der inkrementellen Sequenz zu haben! (Offensichtlich macht es wenig Sinn, eine Folge nach 4 und dann nach 2 zu sortieren.)
Hier sind einige gängige Delta-Sequenzen.
Das erste Inkrement ist das ursprünglich von Donald Shell vorgeschlagene Inkrement, das um die Hälfte auf 1 reduziert wird. Untersuchungen zufolge beträgt die Zeitkomplexität bei Verwendung des Hill-Inkrements immer noch O(n2).
Das zweite Inkrement Hibbard: {1, 3, ..., 2^k-1}. Die zeitliche Komplexität dieser inkrementellen Sequenz beträgt ungefähr O(n^1,5).
Das dritte Inkrement Sedgewick-Inkrement: (1, 5, 19, 41, 109,...), die generierte Sequenz ist entweder 9*4^i - 9*2^i + 1 oder 4^ i - 3* 2^i + 1.
Algorithmusstabilität
Wir alle wissen, dass die Einfügungssortierung ein stabiler Algorithmus ist. Bei der Shell-Sortierung handelt es sich jedoch um einen Mehrfacheinfügungsprozess. Bei einer Einfügung können wir sicherstellen, dass die Reihenfolge derselben Elemente nicht verschoben wird, bei mehreren Einfügungen können jedoch dieselben Elemente in verschiedenen Einfügungsrunden verschoben werden, und letztendlich wird die Stabilität zerstört. Daher ist der Shell-Sortieralgorithmus nicht stabil .
Algorithmus-anwendbare Szenarien
Obwohl die Shell-Sortierung schnell ist, handelt es sich doch um eine Einfügungssortierung, und ihre Größenordnung ist nicht so schnell wie die schnelle Sortierung mit aufsteigendem Stern O(n㏒n). Angesichts großer Datenmengen ist die Shell-Sortierung kein guter Algorithmus. Für kleine bis mittlere Datenmengen ist es jedoch vollkommen in Ordnung.
Ausführlichere Erläuterungen zum Hill-Sortieralgorithmus und zugehörige Artikel zur Java-Code-Implementierung finden Sie auf der chinesischen PHP-Website!
