插入排序的改进。递减增量排序算法。
步长为1时就是插入排序。
#include<stdio.h>
void ShellSort(int a[],int n)
{
int i,j,k,temp,gap;
int gaps[]={1,5,13,43,113,297,815,1989,4711,11969,27901,84801,213331};
for(k=0;gap[k]<n;k++)
while(--k>=0)
{
gap = gaps[k];
for(i=gap;i<n;i++)
{
j=i-gap;
temp=a[i];
while((j>=0)&&(a[j]>temp))
{
a[j+gap] = a[j];
j=j-gap;
}
a[j+gap] = temp;
}
}
}
或者：
void shellSort(int* data,size_t size)
{
for(int gap = size/2;gap>0;gap/=2)
for(int i=gap;i<size;++i)
{
int key = data[i];
int j=0;
for(j=i-gap;j>=0&&data[j]>key;j-=gap)
{
data[j+gap] = data[j];
}
data[j+gap] = key;
}
}