一，概念：希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一

二，复杂度：希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多

三：代码

#include<stdio.h>
#include<stdlib.h>
//堆排序用于查找最大值 或者 最小值
void show(int *p, int n)
{
    for (int i = 0; i < n;i++)
    {
        printf("%4d", p[i]);
    }
    printf("\n");
}
void shellsort(int *p, int length)
{
    int d = length / 2;//增量
    while (d >= 1)//增量终止条件
    {
        for (int i = d; d < length && i < length; i++)//最后的位置
        {
            int x = p[i];//备份数据
            int j = i - d;//与其对于的前面的元素
            while (j >= 0 && p[j]>x)//在数组范围内  找到擦入的位置
            {
                p[j + d] = p[j];
                j = j - d;//每次变化
            }
            p[j + d] = x;//交换
        }
        //d = d / 2;
        d--;//增量*设定
    }
}
void main()
{
    int a[8] = { 1, 8, 2, 7, 3, 6, 4, 5 };
    show(a, 8);
    shellsort(a, 8);
    show(a, 8);
}