Временная сложность сортировки Хилла равна O(n*log2n), а пространственная сложность — O(1). Это нестабильный алгоритм сортировки.
Идея: сортировка по холму — это также метод сортировки вставками, который на самом деле является методом групповой вставки. Сначала определите целое число d1 меньше n в качестве первого приращения, разделите все записи в таблице на группы d1, поместите все записи, расстояние которых кратно d1, в одну группу и затем выполните прямую сортировку вставками внутри каждой группы; , берем второе приращение d2 (<d1), повторяем описанную выше группировку и сортировку до тех пор, пока полученное приращение dt=1 (dt<dt-1<...<d2<d1), то есть все записи не будут помещены в той же группы, пока не будет выполнена сортировка прямой вставкой.
Скопируйте код кода следующим образом:
void ShellSort (данные int*, длина int)
{
если (данные == NULL || длина <= 0)
возвращаться;
int d = длина/2; // размер шага
в то время как (д)
{
for(int i = 0; i < d; ++i) //Разделение на группы в соответствии с размером шага и сортировка вставкой в каждой группе
{
//Сортировка вставкой
for(int j = i+d; j <length; j +=d)
{
если (данные[j] <данные[j -d])
{
int temp = данные [j]; // дозорный
int k = jd;
for(; k >=0&& temp < data[k]; k -=d)
{
данные[к+д] =данные[к];
}
данные [к+д] = темп;
}
}
}
д = д/2;
}
}