Maison > Article > interface Web > JS implémente le tri Hill
Cet article présente principalement l'implémentation du tri Hill dans JS, qui a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer
Le tri Hill est essentiellement un tri par insertion. mais la séquence est regroupée à intervalles égaux et le tri par insertion est effectué dans chaque groupe. Cette optimisation réduit la complexité temporelle d'origine de O(n^2) à O(nlogn).
Le tri Hill consiste à regrouper les tableaux à certains intervalles, puis à effectuer un tri par insertion dans chaque groupe ; puis à réduire progressivement l'intervalle et à effectuer un tri par insertion dans chaque groupe... jusqu'à ce que l'intervalle est égal à 1, faites un tri par insertion et terminez.
La question est alors de savoir quelle doit être la taille de l'intervalle et comment le réduire ? Habituellement, nous prenons l'intervalle initial comme étant la moitié de la longueur de la séquence : gap = longueur/2, et le réduisons sous la forme de gap = gap/2. L'ensemble du processus est illustré en détail ci-dessous.
Le tableau d'origine est le suivant :
Prenez d'abord l'intervalle comme écart = longueur/2 = 4, et divisez le tableau en 4 groupes comme suit, Implémenter le tri par insertion pour chaque groupe :
Pour le premier tri, les éléments plus petits de chaque groupe sont déplacés vers une position relativement avant (ce l'état peut Il est appelé n-trié, c'est-à-dire regroupé avec n comme espace et ordonné). Il est concevable qu'un tableau relativement ordonné soit plus propice au tri ultérieur. Continuez ensuite à regrouper, gap = gap/2 = 2, implémentez le tri par insertion pour chaque groupe :
Continuez à regrouper le tableau, gap = gap/2 = 1 , c'est-à-dire que tous les éléments forment un groupe, et l'algorithme de tri par insertion est terminé :
utilisation de la boucle interne Le tri par insertion est fondamentalement le même que le tri par insertion ordinaire, sauf que la taille du pas de chaque mouvement devient un espace au lieu de 1 :
// shellSort
function shellSort(arr) {
for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
// 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
for(let i = gap; i 0; j -= gap) {
if(temp >= arr[j-gap]) {
break;
}
arr[j] = arr[j-gap];
}
arr[j] = temp;
}
}
return arr;
}
// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));
Ce qui précède représente l'intégralité du contenu de cet article .J'espère que cela sera utile à l'apprentissage de tout le monde. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !
Recommandations associées :
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!