1.4 希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

1. 算法步骤
   选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
   按增量序列个数 k，对序列进行 k 趟排序；
   每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2. 动图演示

   
   image.gif

int shsort(int s[], int n)    /* 自定义函数 shsort()*/
{
    int i,j,d;
    d=n/2;    /*确定固定增虽值*/
    while(d>=1)
    {
        for(i=d+1;i<=n;i++)    /*数组下标从d+1开始进行直接插入排序*/
        {
            s[0]=s[i];    /*设置监视哨*/
            j=i-d;    /*确定要进行比较的元素的最右边位置*/
            while((j>0)&&(s[0]<s[j]))
            {
                s[j+d]=s[j];    /*数据右移*/
                j=j-d;    /*向左移d个位置V*/
            }
            s[j + d]=s[0];    /*在确定的位罝插入s[i]*/
        }
        d = d/2;    /*增里变为原来的一半*/
    }
return 0;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int a[11],i;    /*定义数组及变量为基本整型*/
        printf("请输入 10 个数据：\n");
        for(i=1;i<=10;i++)
        scanf("%d",&a[i]);    /*从键盘中输入10个数据*/
        shsort(a, 10);    /* 调用 shsort()函数*/
        printf("排序后的顺序是：\n");
        for(i=1;i<=10;i++)
        printf("%5d",a[i]);    /*输出排序后的数组*/
        printf("\n");
        
    }
    return 0;
}