希尔排序的算法代码

时间:2021-05-19

希尔排序的时间复杂度为O(n*log2n) 空间复杂度为O(1)是一种不稳定的排序算法

思想:希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序;然后,取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

复制代码 代码如下:
void ShellSort(int* data ,int length)
{
if( data == NULL || length <= 0 )
return;

int d = length/2; //步长
while( d )
{
for(int i = 0 ; i < d ; ++i) //根据步长分成组,对每组进行插入排序
{
//插入排序
for(int j = i+d; j <length ; j +=d )
{
if( data[j] < data[j -d])
{
int temp = data[j]; //哨兵
int k = j-d;
for(; k >=0&& temp < data[k]; k -=d)
{
data[k+d] =data[k];
}
data[k+d] =temp;
}
}
}
d = d/2;
}
}

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章