The time complexity of Hill sorting is O(n*log2n) and the space complexity is O(1). It is an unstable sorting algorithm.
Idea: Hill sorting is also an insertion sorting method, which is actually a grouping insertion method. First, determine an integer d1 less than n as the first increment, divide all the records in the table into d1 groups, put all records whose distance is a multiple of d1 into the same group, and perform direct insertion sorting within each group; then , take the second increment d2 (<d1), repeat the above grouping and sorting, until the taken increment dt=1 (dt<dt-1<...<d2<d1), that is, all records are placed in the same group until direct insertion sort is performed.
Copy the code code as follows:
void ShellSort(int* data,int length)
{
if( data == NULL || length <= 0 )
return;
int d = length/2; //step size
while(d)
{
for(int i = 0; i < d; ++i) //Divide into groups according to the step size, and insert sort each group
{
//Insertion sort
for(int j = i+d; j <length ; j +=d )
{
if(data[j] < data[j -d])
{
int temp = data[j]; //sentinel
int k = jd;
for(; k >=0&& temp < data[k]; k -=d)
{
data[k+d] =data[k];
}
data[k+d] =temp;
}
}
}
d = d/2;
}
}