La complejidad temporal de la clasificación Hill es O (n * log2n) y la complejidad espacial es O (1). Es un algoritmo de clasificación inestable.
Idea: la clasificación Hill también es un método de clasificación por inserción, que en realidad es un método de inserción por agrupación. Primero, determine un número entero d1 menor que n como primer incremento, divida todos los registros de la tabla en grupos d1, coloque todos los registros cuya distancia sea múltiplo de d1 en el mismo grupo y luego realice una clasificación por inserción directa dentro de cada grupo; , tome el segundo incremento d2 (<d1), repita la agrupación y clasificación anterior, hasta que el incremento tomado dt=1 (dt<dt-1<...<d2<d1), es decir, todos los registros se coloquen en el mismo grupo hasta que se realice la ordenación por inserción directa.
Copie el código de código de la siguiente manera:
void ShellSort(int* datos,int longitud)
{
si (datos == NULL || longitud <= 0)
devolver;
int d = longitud/2; //tamaño del paso
mientras(d)
{
for(int i = 0; i < d; ++i) //Dividir en grupos según el tamaño del paso e insertar ordenar cada grupo
{
//ordenación por inserción
para (int j = i+d; j <longitud; j +=d)
{
si(datos[j] <datos[j -d])
{
int temp = datos[j]; //centinela
int k = jd;
para(; k >=0&& temp < datos[k]; k -=d)
{
datos[k+d] =datos[k];
}
datos[k+d] =temp;
}
}
}
d = d/2;
}
}