Zwei Beispiele für den JavaScript-Sortieralgorithmus Hill Sorting

Zwei Beispiele für den JavaScript-Sortieralgorithmus Hill Sorting_Grundkenntnisse

WBOY

Freigeben： 2016-05-16 16:53:18

Original

1663 Leute haben es durchsucht

Einfügungssortierung ist hocheffizient, wenn mit fast sortierten Daten gearbeitet wird, das heißt, sie kann die Effizienz linearer Sortierung erreichen.
Aber die Einfügungssortierung ist im Allgemeinen ineffizient, da die Einfügungssortierung Daten jeweils nur um ein Bit verschieben kann.
Hill Sorting ist nach seinem Erfinder Donald Shell benannt und der Algorithmus wurde 1959 veröffentlicht. Einige ältere Lehrbücher und Referenzhandbücher nannten den Algorithmus Shell-Metzner, der den Namen Marlene Metzner Norton enthält, aber laut Metzner selbst „habe ich nichts für diesen Algorithmus getan und mein Name sollte nicht im Algorithmus erscheinen.“ >

Zwei Beispiele für den JavaScript-Sortieralgorithmus Hill Sorting_Grundkenntnisse
Die Grundidee der Hill-Sortierung: Nehmen Sie zunächst eine Ganzzahl d1 kleiner als n als erstes Inkrement und teilen Sie alle Datensätze in der Datei in d1-Gruppen auf. Alle Datensätze, deren Abstand ein Vielfaches von d1 ist, werden in derselben Gruppe platziert. Führen Sie zuerst eine direkte Einfügungssortierung innerhalb jeder Gruppe durch. Nehmen Sie dann das zweite Inkrement d2 < ist, bis alle Datensätze für die direkte Einfügungssortierung in derselben Gruppe platziert werden.

Diese Methode ist im Wesentlichen eine gruppierte Einfügemethode.

Beispiel 1:

Code kopieren Der Code lautet wie folgt:

/**
* Hill-Sortierung, auch bekannt als absteigender inkrementeller Sortieralgorithmus, ist eine effizientere und verbesserte Version der Einfügungssortierung. Hill-Sortierung ist ein instabiler Sortieralgorithmus.
*
* Die Hill-Sortierung schlägt eine verbesserte Methode vor, die auf den folgenden zwei Eigenschaften der Einfügungssortierung basiert:
*
* Die Einfügungssortierung ist hocheffizient, wenn mit nahezu sortierten Daten gearbeitet wird Eine lineare Sortierung kann erreicht werden
* aber die Einfügungssortierung ist im Allgemeinen ineffizient, da die Einfügungssortierung Daten jeweils nur um ein Bit verschieben kann
*
*/

function shellSort( list ) {
var gap = Math.floor( list.length / 2 );

while( gap > 0 ) {

for( i = Lücke; i < list.length; i ) {
temp = list[i];

for( j = i; j >= Lücke && Liste[ j - Lücke ] > temp; j -= Lücke ) {
list[j] = list[j - Lücke];
list[j] = temp;
}

Lücke = Math.floor( Lücke / 2 );
}

return list;
};

// test
var arr = [2, 1, 3 , 12, 5, 66, 23, 87, 15, 32];

shellSort(arr);

Beispiel 2:

Code kopieren Der Code lautet wie folgt: