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

算法步骤

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

第一趟希尔排序，间隔为4

image.png

第二趟排序：间隔是2

image.png

有人问，这个间隔怎么确定，这是个数学难题，至今没有解答。但是通过大量的实验，还是有个经验值。

希尔排序比插入排序快很多，它是基于什么原因呢？当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。

void xier(){
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    int n = sizeof(a) / sizeof(int);
    int i, j, get;
    int h = 0;
    while (h <= n) {
        h = 3*h + 1;
    }
    while (h >= 1)
    {
        for (int i=h; i<10; i++) {
            int p = a[i];
            for (int j=i; j>=i&&p<a[j-h]; j-=h) {
                a[j] = p;
            }
        }
        h = (h - 1) / 3;                    // 递减增量
    }
    printf("希尔排序结果：");
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}