8.希尔排序

推荐视频https://www.bilibili.com/video/av17004970/?from=search&seid=17055254545953111032
非常形象的演示了希尔排序的过程.
希尔排序尝试与之前h个元素进行比较，这样通过将h从一个很大的值逐渐缩小到1，一步步将一个无序数组变成有序性更强的数组。

参考zju-mooc-数据结构

图中的注意是说，比如经过3间隔排序后的数组 依然满足5间隔有序，同理经过1间隔排序后的数组依然是满足3间隔有序的。

这个例子是说8间隔有序的话，那么4,2都可能有序，那么进行8,4,2间隔的排序就是一种浪费.

void shellSort(T arr[], int n){
    //根据给定的数组大小n来计算对应递增序列中的最大值
    int h = 1;
    while( h < n/3 )
        h = h * 3 + 1;
    /*
    *   其实在这里我觉得应该添加这样一段代码：
    *   if(n == h)
    *       h /= 3;
    *   因为当n等于h的话，进入下面的循环后 for( int i = h; i < n; i++ ) 会退出
    *   不过知道就行了，实际上对性能没什么影响
    */
    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    while( h >= 1 ){
        for( int i = h; i < n; i++ ){
            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for(j = i; j >= h && e < arr[j-h]; j -= h)
                arr[j] = arr[j-h];
            arr[j] = e;
        }
        h /= 3;
    }
}

其他与前次代码相同，测试结果为：

希尔排序非常高效.

希尔排序时间复杂度的分析是比较难的，我们选取不同的让h递减的序列，它的复杂度也是不同的.
increment sequence: 1, 4, 13, 40, 121, 364, 1093...使用这个序列 时间复杂度为O(n^3/2)
希尔排序的时间复杂度比O(n^2)要低，但比O(nlogn)要高一些，不过它的实现比较简单.
不过对于排序算法来讲它的最优时间复杂度是O(nlogn)这个级别的.