排序算法大荟萃——希尔（Shell）排序算法

1、基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先再各族中进行直接插入排序，然后取第二个增量d2<d1重复上述的分组和排序过程，知道所取的增量dt=1（dt<dt-1<...<2<1）,即所有记录放在同一组中进行直接插入排序为止。

如：待排序文件有10个记录，则增量序列的取值依次为5,3,2,1.（增量d=(d+1)/2）

2、代码如下：

void ShellSort1(int * data,int left,int right)
{
int len=right-left+1;
int d=len;
while(d>1)
{
d=(d+1)/2;
for(int i=left;i<right+1-d;i++)
{
if(data[i+d]<data[i])
{
int tmp=data[i+d];
data[i+d]=data[i];
data[i]=tmp;
}
}
}
}

void ShellSort2(int *data,int len)
{
int d=len;
while(d>1)
{
d=(d+1)/2;
for(int i=0;i<len-d;i++)
{
if(data[i+d]<data[i])
{
int tmp=data[i+d];
data[i+d]=data[i];
data[i]=tmp;
}
}
for(int i=0;i<10;i++)
printf("%5d",data[i]);
printf("\n");

}
}

希尔排序是一种不稳定排序，时间复杂度O（n log n）,空间复杂度O(1)