Explication détaillée du tri de l'algorithme JS Hill

L'algorithme Hill est également une sorte de tri par insertion en principe. Avant de comprendre l'algorithme Hill, vous devez comprendre le tri par insertion ; nous avons déjà partagé avec vous Explication détaillée du tri par insertion JS, j'espère que cela l'article peut aider tout le monde.

Principe :
Le tri en colline regroupe les données en fonction du tri par insertion, divise les données d'origine en plusieurs sous-ensembles, puis trie chacun. Les sous-ensembles sont triés, et ainsi de suite , continuellement divisés en sous-ensembles, jusqu'à ce qu'ils soient finalement complètement triés.

Séquence : [3,5,2,4,7,6,8,9,1]
Divisez d'abord la séquence entière en sous-ensembles en fonction de l'espace et triez les sous-ensembles (l'espace est ; généralement Math.floor(arr.length/2))
gap:4
Le sous-ensemble divisé est : 3,7,1 5,6 2,8 4,9 est le sous-ensemble
Après avoir trié les sous-ensembles : 1,3,7 5,6 2,8 4,9
Le nombre est : [1,5,2,4,3,6,8,9,7]

Modifier l'écart valorisez et triez à nouveau
écart : 2
……..
Arrêtez jusqu'à ce que la valeur de l'écart soit 0

Implémentation du code JS :

var arr=[3,5,2,4,7,6,8,9,1];var gap=Math.floor(arr.length/2);       
while(gap>0){    for(var i=gap;i<arr.length;i++){        var temp=arr[i];        var j=i-gap;        while(j>=0&&arr[j]>temp){
            arr[j+gap]=arr[j];
            arr[j]=temp;
            j-=gap;
        }
        arr[j+gap]=temp;
        }
    gap=Math.floor(gap/2); 
}

输出结果： [1, 2, 3, 4, 5, 6, 7, 8, 9]

Recommandations associées :

Explication détaillée du tri par insertion JS

Exemple d'analyse des algorithmes de tri de base couramment utilisés en JavaScript

Explication détaillée de la déduplication de tableaux javascript et exemples d'algorithmes de tri rapide

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!