首先我们来看插入排序的code demo：

include

void insertSort(int arr[],int len)
{
for(int i=1;i=0&&arr[j]>get)
{
arr[j+1]=arr[j];
j-=1;
}
arr[j+1] = get;
}
}

void printArray(int arr[],int len)
{
for(int i=0;i<len;i++)
printf("%2d ",arr[i]);
printf("\n");
}

main()
{
int arr[] = {3,14,2,11,6,13,9,10,7,4,5,8,1,12};
int len = sizeof arr / sizeof *arr;
printArray(arr,len);
insertSort(arr,len);
printArray(arr,len);

getchar();

}
外套一层间隔逐步缩小的循环，将插入排序中间隔是1的部分改为间隔变量，就变成了希尔排序：

void shellSort(int arr[],int len)
{
for(int gap = len/2;gap>0;gap/=2)
for(int i=gap;i=0&&arr[j]>get)
{
arr[j+gap]=arr[j];
j-=gap;
}
arr[j+gap] = get;
}
}
gap也可以处理为 ……,gap*3+1,……,40,13,4,1的序列：

void shellSort(int arr[],int len)
{
int gap = 0;
while(gap<=len)
gap = gap*3+1;
for(;gap>0;gap=(gap-1)/3)
for(int i=gap;i=0&&arr[j]>get)
{
arr[j+gap]=arr[j];
j-=gap;
}
arr[j+gap] = get;
}
}
插入排序内部也可以写成逐个做插入的形式（冒泡形式）：

void insertSort(int arr[],int len)
{//代码效果参考：http://www.zidongmutanji.com/bxxx/465442.html

for(int i=1;i<len;i++)
{
    for(int j=i;j>0 && arr[j]>arr[j-1];j--)
    {
        int tmp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = tmp;
    }
}

}
void insertSort(int arr[],int len)
{
for(int gap = len/2;gap>0;gap/=2)
for(int i=gap;i=gap && arr[j]<arr[j-gap];j-=gap)
{
int tmp = arr[j];
arr[j] = arr[j-gap];
arr[j-gap] = tmp;
}
}