推荐视频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)这个级别的.
