思路：

希尔排序又称缩小增量排序（diminishing increment sort）,

首先选择一个增量序列（increment sequence）,,其中，, 

按增量序列的个数 t ,执行 t 趟排序；

对于每一趟排序，将 中的每一个位置i,把其上的元素放到中间的正确位置上，可以看出，对于一趟增量的排序，就是对个独立的子数组执行一次插入排序。

希尔排序一般的增量序列是，

时间复杂度：

平均，；最好， ；最坏 ，   (取决于选择的增量序列)

程序：

void shell_sort(int array[],int array_size)
{
    int increment,i,j,tmp;
    for(increment=array_size/2;increment>0;increment/=2)
    {   
        for(i=increment;i<array_size;i++)
        {   
            tmp=array[i];
            for(j=i;j-increment>=0 && tmp<array[j-increment];j-=increment)
            {   
                array[j]=array[j-increment];
            }   
            array[j]=tmp;   
        }   
    }   
}

#include <stdio.h>

int main()
{
    int i;  
    int array[]={100,96,88,75,63,52,41,36,28,19,6,0,-19,-105};
    int array_size=sizeof(array)/sizeof(int);
    printf("Original array:\n");
    for(i=0;i<array_size;i++)
        printf(" %d, ",array[i]);
    printf("\n");
    shell_sort(array,array_size);
    printf("Sorted array:\n");
    for(i=0;i<array_size;i++)
        printf(" %d, ",array[i]);
    printf("\n");
    return 0;
}

参考：

https://www.runoob.com/w3cnote/shell-sort.html