La complexité temporelle du tri Hill est O(n*log2n) et la complexité spatiale est O(1). C'est un algorithme de tri instable.
Idée : le tri Hill est également une méthode de tri par insertion, qui est en fait une méthode d'insertion de regroupement. Tout d'abord, déterminez un entier d1 inférieur à n comme premier incrément, divisez tous les enregistrements de la table en groupes d1, placez tous les enregistrements dont la distance est un multiple de d1 dans le même groupe et effectuez ensuite un tri par insertion directe dans chaque groupe ; , prenez le deuxième incrément d2 (<d1), répétez le regroupement et le tri ci-dessus, jusqu'à ce que l'incrément pris dt=1 (dt<dt-1<...<d2<d1), c'est-à-dire que tous les enregistrements soient placés dans le même groupe jusqu’à ce que le tri par insertion directe soit effectué.
Copiez le code comme suit :
void ShellSort (int* données,int longueur)
{
si( données == NULL || longueur <= 0 )
retour;
int d = longueur/2; //taille du pas
tandis que(d)
{
for(int i = 0; i < d; ++i) // Divisez en groupes en fonction de la taille du pas et insérez un tri pour chaque groupe
{
//Tri par insertion
pour(int j = i+d; j <longueur ; j +=d )
{
si (données [j] < données [j -d])
{
int temp = données[j]; //sentinelle
int k = jd;
pour(; k >=0&& temp < données[k]; k -=d)
{
données[k+d] =données[k];
}
données[k+d] =temp;
}
}
}
d = d/2;
}
}