Qu'est-ce que le tri Hill

Le tri Hill est une sorte de tri par insertion, également connu sous le nom de « tri incrémentiel réducteur ». Il s'agit d'une version plus efficace et améliorée de l'algorithme de tri par insertion directe qui est un algorithme de tri non stable. La méthode est due à "D.L.Shell" qui a été proposée en 1959 et porte son nom.

Tri par collines

Divise un ensemble d'éléments à trier en plusieurs éléments à certains intervalles Séquences sont insérés et triés séparément. L'"intervalle" défini au début est plus grand et l'intervalle est progressivement réduit à chaque tour de tri jusqu'à ce que "l'intervalle" soit 1, c'est-à-dire que la dernière étape consiste à effectuer un tri par insertion simple

Complexité temporelle : incrément de somme Sélection de séquence liée au tri non stable

Introduction :

Le tri Hill (Shell's Sort) est une sorte de tri par insertion, également connu sous le nom de "Tri par incrément décroissant" (Tri par incrément décroissant ), qui est une version directe plus efficace et améliorée de l'algorithme de tri par insertion. Le tri Hill est un algorithme de tri non stable. Cette méthode doit son nom à sa proposition par D.L. Shell en 1959.

Le tri Hill consiste à regrouper les enregistrements par un certain incrément de l'indice et à trier chaque groupe à l'aide de l'algorithme de tri par insertion directe ; à mesure que l'incrément diminue progressivement, chaque groupe contient de plus en plus de mots-clés. à 1, le fichier entier est divisé en un seul groupe et l'algorithme se termine.

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!