概念

希尔排序(Shell Sort)：是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

原理

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作如下：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1（一般的初次取序列的一半为增量，以后每次减半，直到增量为1）；
2. 按增量序列个数k，对序列进行k 趟排序；

3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
   例子：

   
   图片.png
   

   在上面这幅图中：
   初始时，有一个大小为 10 的无序序列。
   在第一趟排序中，我们不妨设 t1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
   接下来，按照直接插入排序的方法对每个组进行排序。
   在第二趟排序中，我们把上次的 t1 缩小一半，即 t2 = t1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
   按照直接插入排序的方法对每个组进行排序。
   在第三趟排序中，再次把 t2 缩小一半，即t3 = t2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
   按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

算法描述（C语言）

void shell_insert(int *a, int len, int t) {
    for (int i = t; i < len; i++) { //从第t个元素开始
        int j = i - t;
        int temp = a[i];
        while (j >= 0 && a[j] > temp) { //根据增量t分组 插入排序
            a[j + t] = a[j];
            j -= t;
        }
        if (j != i - t) {
            a[j + t] = temp;
        }
    }
}

void sheel_sort(int *a, int len){
    int t = len/2;
    while (t >= 1) { //增量是1时停止排序
        shell_insert(a, len, t);
        t = t/2;
    }
}

int main() {
    int a[] = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
    int len = sizeof(a)/sizeof(int);
    sheel_sort(a, len);
    for (int i = 0; i < len; i++) {
        printf("%d\n", a[i]);
    }
    return 0;
}

算法稳定性

希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。

算法分析

希尔排序的时间复杂度依赖增量， 希尔排序的时间复杂度会比o(n²)好一些。