Shells Sort ist ein sehr "magischer" Sortieralgorithmus. Es soll "magisch" sein, weil niemand klar erklären kann, was seine Leistung tatsächlich erreichen kann. Hügelsortierung, weil dl. Shell wurde nach dem Vorschlag von 1959 benannt. Seit dem Auto Hoare wurde 1962 eine schnelle Sortierung vorgeschlagen, es wird im Allgemeinen eine schnelle Sortierung verwendet, da sie einfacher ist. Viele Mathematiker suchen jedoch immer noch unermüdlich nach der besten Komplexität der Hügelsortierung. Als gewöhnliche Programmierer können wir die Ideen von Hill lernen.
Übrigens, bevor die Sortierung von Hügeln erschien, gab es in der Computerwelt eine allgemeine Sichtweise, dass "Sortieren von Algorithmen O (N2) nicht durchbrechen können". Die Entstehung von Hillsorting brach diesen Fluch, und bald wurden Algorithmen wie das schnelle Sortieren nacheinander veröffentlicht. In diesem Sinne führt uns die Sortierung von Hills zu einer neuen Ära.
Algorithmusübersicht/Ideen
Der Vorschlag zur Sortierung von Hügeln basiert hauptsächlich auf den folgenden zwei Punkten:
1. Der Insertions -Sortieralgorithmus kann ungefähr die Komplexität von O (N) erreichen und extrem effizient, wenn das Array im Grunde genommen geordnet wird.
2. Die Insertionssortierung kann jedoch nur Daten jeweils um ein Bit verschieben, und die Leistung verschlechtert sich schnell, wenn das Array groß ist und im Grunde gestört ist.
Basierend darauf können wir eine gruppierte Sortiermethode verwenden, nämlich die spezifische Methode: (Nehmen Sie ein Array von 16 Elementen als Beispiel.)
1. Wählen Sie ein Inkrementdelta, das größer als 1 ist, und wählen Sie das Subaarrray im Array mit diesem Inkrement für die direkte Einfügungssortierung aus. Wenn beispielsweise das Inkrement 5 beträgt, werden die Elemente mit den Einweisen 0, 5, 10, 15 sortiert.
2. Halten Sie das Increment Delta und bewegen Sie das erste Element wiederum zum Einfügen und Sortieren, bis die Runde abgeschlossen ist. Für das obige Beispiel werden die Arrays [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] nacheinander sortiert.
3. Reduzieren Sie das Inkrement und wiederholen Sie den obigen Vorgang kontinuierlich, bis das Inkrement auf 1 abnimmt. Offensichtlich ist das letzte Mal die direkte Sortierung direkter Einfügung.
4. Sortieren ist abgeschlossen.
Wie aus oben ersichtlich ist, nimmt das Inkrement ständig ab, sodass die Sortierung des Hügels erneut als "reduziertes Inkrementsortieren" bezeichnet wird.
Code -Implementierung
Paketsorte; 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}; Druck (Daten); ShellSort (Daten); Druck (Daten); } public static void ShellSort (int [] Daten) {// Berechnen Sie den maximalen H -Wert int H = 1; while (h <= data.length / 3) {H = H * 3 + 1; } while (h> 0) {für (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; } Daten [j + h] = tmp; Druck (Daten); }} // Berechnen Sie den nächsten H -Wert H = (h - 1) / 3; }} public static void print (int [] data) {für (int i = 0; i <data.length; i ++) {System.out.print (data [i]+"/t"); } System.out.println (); }} Auslaufergebnisse:
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 7 8 9 1 2 3 4 5 6 7 8 9 9 9
Algorithmus Leistung/Komplexität
Die inkrementellen Sequenzen, die von Hill sortiert sind, können jederzeit eingenommen werden, und die einzige Anforderung besteht Eine unterschiedliche Sequenzauswahl wird jedoch einen enormen Einfluss auf die Leistung des Algorithmus haben. Der obige Code zeigt zwei Schritte.
Denken Sie daran: Es ist am besten, keine gemeinsamen Faktoren als 1 für zwei Elemente in der inkrementellen Sequenz zu haben! (Offensichtlich ist das Sortieren von 2 nacheinander nicht sehr bedeutungsvoll).
Im Folgenden finden Sie einige häufige inkrementelle Sequenzen.
Das erste Inkrement ist das ursprünglich von Donald Shell vorgeschlagene, d. H. Die Falte wird auf 1 reduziert. Nach Forschungen unter Verwendung von Hill -Inkrementen beträgt die zeitliche Komplexität immer noch O (N2).
Der 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 eine Sequenz entweder 9*4^i - 9*2^i + 1 oder 4^i - 3*2^i + 1 erzeugt.
Algorithmusstabilität
Wir alle wissen, dass das Insertionssortieren ein stabiler Algorithmus ist. Die Shell -Sortierung ist jedoch ein Prozess mehrerer Einfügungen. In einer Insertion können wir sicherstellen, dass die Reihenfolge derselben Elemente nicht bewegt wird, aber in mehreren Einfügen ist es durchaus möglich, dass dieselben Elemente in verschiedenen Einfügungsrunden bewegt werden und die Stabilität schließlich zerstört wird. Daher ist die Shell -Sortierung kein stabiler Algorithmus.
Algorithmus anwendbarer Szenarien
Obwohl die Shell -Sortierung schnell ist, ist es doch ein Einsatz sortieren und seine Größenordnung ist nicht so gut wie der aufsteigende Stern - das schnelle Sortieren von O (NN) ist schnell. Die Shell -Sortierung ist angesichts einer großen Datenmenge kein guter Algorithmus. Es ist jedoch durchaus möglich, kleine und mittelgroße Daten zu verwenden.