希尔排序

原理

其实，希尔排序本质也就是直接插入算法的升级，希尔的基本思想，就是先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量大小再进行排序，待整个序列中的元素基本有序（增量足够小，通常为1）时，再对全体元素进行一次直接插入排序

步长选择

其实步长（增量）的选择没有统一规定，也没绝对的规律。只要满足最后一个步长（增量）为1即可。
已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该串行的项来自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 这两个算式[1].这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”

而我们在实践中，如果没特殊需要，一般增量的选取规则为：
第一次取总长度的一半，第二次取一半的一半，依次累推直到步长为1为止。
这样不仅简单，也能利用希尔算法进行排序。

代码

void ShellSort(int arr[], int n)
{
    int i, j, k;
    int temp, gap;
    
    for (gap = n / 2; gap > 0; gap /= 2) //步长的选取
    {
        for (i = 0; i < gap; i++)        //直接插入排序原理
        {
            for (j = i + gap; j < n; j += gap)    //每次加上步长，即按列排序。
                if (arr[j] < arr[j - gap])
                {
                    temp = arr[j];
                    k = j - gap;
                    while (k >= 0 && arr[k] > temp) //记录后移，查找插入位置
                    {
                        arr[k + gap] = arr[k];
                        k -= gap;
                    }
                    arr[k + gap] = temp;  //找到位置插入
                }
        }
    }
}

算法分析

希尔排序平均时间复杂度为O(n(logn)^2) 较为不稳定