Zwei Beispiele für den JavaScript-Sortieralgorithmus Hill Sorting_Grundkenntnisse

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.“ >

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:

Stellungnahme：

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn