1. 原理

首先回忆插入排序

这篇文章中讲的插入排序，相当于从数组第二个元素开始，依次将这些元素插入到该元素左边的已经有序的数组中，而这种方法我们称之为直接插入排序。

直接插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。

而希尔排序是在直接插入排序的基础上做了些优化。
首先根据某种策略设定一个增量increment，然后把原数组中所有距离为increment的元素分到同一组中，然后对每一组分别进行直接插入排序，进行完成后视作完成了一趟排序。然后再按某种策略减小increment并重复上述过程，直到increment减到1，可以看出这时候所有元素都被分到了一组中，所以这最后一趟排序就相当于普通的直接插入排序，但因为前面所做的工作，此时的数组已经处于预排序过的状态了，所以最后一趟调整也变得十分轻松，这就是希尔排序性能优越的体现。下图展示了希尔排序的过程：

希尔排序的精髓在于使得待排序序列变得接近有序，因为在前面gap较大的时候，通常是将一个处于序列前面的元素和一个处于序列后面的元素进行比较，如果比较之前是小的在后大的在前的话，比较之后就可以把这两个元素交换到应该在的那一部分去。这个方法可能听起来比较玄学，但不管怎样经过大佬们的推导希尔排序的时间复杂度为O($ N^{1.3} $ ~ $ N^2 $) 。空间复杂度为O(1)。是一种不稳定的排序算法。

2. 代码

注意代码中 i 初始化为 increment，且每次自增1，用下图来解释。

图中增量为5，所以下标为5的元素为黑3。可知黑3之前的所有元素都是各自组中的第一个元素所以不用插入，故 i 从 increment 开始遍历。而之后的每个元素都是要插入各自组的元素，所以让 i 自增1即可。

#include <stdio.h>
#include <stdlib.h>

void shellSort(int* arr, int size) {
    int increment = size / 3 - 1;
    int val;
    int i, j;

    while (increment > 0) {
        for (i = increment; i < size; i++) {
            val = arr[i];
            for (j = i; j - increment >= 0; j -= increment) {
                if (val < arr[j - increment]) {
                    arr[j] = arr[j - increment];
                }
            }
            arr[j] = val;
        }
        increment = increment / 3 - 1;
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {2, 4, 1, 1, 7, 9, 3, 6, 5, 8};
    int i;
    shell_sort(arr, sizeof(arr) / sizeof(int));
    for(i = 0; i < (sizeof(arr)/sizeof(int)); i++) 
        printf("%d\n", arr[i]);
    return 0;
}