希尔排序的理解
希尔排序是插入排序的一种高效算法,递增量排序。我理解为步数排序
因为每次进行一次循环的时候,会给这次循环一个跨度(也就是你一次能迈多少步)
void Sort(int a[],int length)
{
int step=0;
/*
这个while循环,目的是找出对于当前数组下,最大的步数,也就是最多能扩多少,
到最后跳出循环的时候,step就是此时最大的跨度(1,4,13……)
*/
while(step<length)
{
step=3*step+1;
}
while(step>=1)
{
/*
当step=1的时候,说明此时的跨度为1,也就是说他现在已经是在一步一步的走了
,所以说是最后的比较,也是最后的一次循环了
*/
for(int i=step; i<n; i++)
{
/*从当前步数开始,与后面的i-step做比较
*/
int get=a[i];//手里拿到的
int j=i-step;//待比较的
while(j>=0&&get<a[j])
{//插入排序不多说
a[j+1]=a[j];
j-=step;
}
a[j+step]=get;//因为跳出while循环的时候是个临界值,所以需要恢复到最后一个状态值
}
/*
每次循环过后步数都会按照规则进行缩小
*/
step=(step-1)/3;
}
}