A complexidade de tempo da classificação Hill é O(n*log2n) e a complexidade do espaço é O(1).
Idéia: a classificação Hill também é um método de classificação por inserção, que na verdade é um método de inserção de agrupamento. Primeiro, determine um número inteiro d1 menor que n como o primeiro incremento, divida todos os registros da tabela em grupos d1, coloque todos os registros cuja distância seja um múltiplo de d1 no mesmo grupo e, em seguida, execute a classificação por inserção direta dentro de cada grupo; , pegue o segundo incremento d2 (<d1), repita o agrupamento e classificação acima, até que o incremento obtido dt=1 (dt<dt-1<...<d2<d1), ou seja, todos os registros sejam colocados no mesmo grupo até que a classificação por inserção direta seja executada.
Copie o código do código da seguinte forma:
void ShellSort (int* dados, comprimento interno)
{
if(dados == NULL || comprimento <= 0 )
retornar;
int d = comprimento/2; //tamanho do passo
enquanto(d)
{
for(int i = 0; i < d; ++i) //Divide em grupos de acordo com o tamanho do passo e insira, classifique cada grupo
{
//Classificação de inserção
for(int j = i+d; j <comprimento; j +=d)
{
if(dados[j] <dados[j -d])
{
int temp = dados[j]; //sentinela
int k = jd;
for(; k >=0&& temp < dados[k]; k -=d)
{
dados[k+d] =dados[k];
}
dados[k+d] =temp;
}
}
}
d = d/2;
}
}