希尔排序

本文将用图例介绍希尔排序的过程，和经典的优化板子

算法思想

对 n 个序列进行分组，每组内的下标是等差数列，其公差就是增量，每一组的等差数列的公差相等，然后对每组序列进行直接插入排序，然后将增量缩小（例如：n/2、n/4、n/8,…）直至每组元素只有1个，然后再进行一次直接插入排序。

直接插入排序对于部分有序的序列效率很高

一个简单的例子：

算法特性

时间复杂度：希尔排序的平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是O(n^3/2)

空间复杂度：O（1）

稳定性：不稳定

算法模板

void shell_sort(){
    // 分组
    for(int d = n / 3 ; d ; d = d == 2 ? 1 : d / 3){
        // start是每组的第一个元素的位置
        for(int start = 0 ; start < d ; start++){
            // 直接插入排序(找到组内第二个元素)
            for(int i = start + d ; i < n ; i += d){
                int base = q[i] , j = i;

                while(j > start && q[j - d] > base){
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = base;
            }
        }
    }
}