1. 希尔排序思想
希尔排序(Shell Sort)是插入排序的一种，是直接插入排序算法的一种更高效的改进版本。具体高效在何处呢？
前面俺讲插入排序的时候，我们会发现一个很费劲的事儿，如果已排序的分组元素为{2,5,6,7,8,9}，未排序的分组 元素为{1}。
我们需要拿着1从后往前，依次和2,5,6,7,8,9进行交换位置，才能完成真正的插入，每次交换只能和相邻的元素交换位置，这样比实在是效率低下。但是，在插入排序时俺说了折半插入，这算是一种优化，但是如果我要是将1插入到2,5,1,7,8,9当中，是不是就不行啦？
那我可不可以这样做呢？
把1放到更前面的位置，比如一次交换就能把1插到6和7之间，这样一次交换1就向前走了3个位置，可以减少交换的次数，然后再通过一次交换，直接结束排序。这样的需求如何实现呢？接下来我们来看看希尔排序的原理。
2. 希尔排序详解
排序原理：
选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
对分好组的每一组数据完成插入排序；
减小增长量，最小减为1，重复第二步操作。
增长量ans：我们这里采用以下规则
【第一趟排序】
初始增量为ans = length/2 = 4，即将整个数组划分为4个子组，分别为4,6，8,2，9,6，7,1
将每个子组独立的看为一个要排序的数组，然后分别进行直接排序。
可以看到，每个子序列现在已经有序了。但是将每个子序列回归放到整个数组中，发现整个数组还是乱序的。我们接着进行第二趟排序。
【第二趟排序】
二次增量为ans = 4/2 = 2，即将整个数组划分为4个子组，分别为4,6,6,9，2,1,8,7
然后在分别对两个子组进行插入排序
【第三趟排序】
第三次增量为ans = 2/2 = 1，即将每个元素看成一组，子序列合并为一组，4,1,6,2,6,7,9,8。
其实，这就是相当于直接插入排序。但是，经过第一趟、第二趟的处理之后，此时第三趟要排序的数组对比于原数组，我们发现它其实是被粗略调整过了，数组在一定程度上变得相对有序了。
此时，仅仅需要对以上数列简单微调，无需大量移动操作即可完成整个数组的排序。
3. 代码实现
public static void shellSort(Integer[] arr) {
//根据数组长度，确定增长量ans
int ans = 1;
while (ans < arr.length/2) {
ans = 2 * ans + 1;
}
while (ans >= 1) {
//找到待插入的元素
for (int i = ans; i < arr.length; i++) {
//待插入的元素插入到分组的有序序列中
for (int j = i; j >= ans; j-=ans) {
//待插入的元素时arr[j],比较arr[j-ans]
if(arr[j] < arr[j-ans]) {
int temp = arr[j];
arr[j] = arr[j-ans];
arr[j-ans] = temp;
}else {
//待插入元素在分组中已有序
break;
}
}
}
//减小ans的值
ans = ans / 2;
}
}
4. 复杂度分析
希尔排序，利用分组粗调的方式减少了直接插入排序的工作量，使得算法的平均时间复杂度低于0(n^2)。
【时间复杂度】O(nlogn)
【空间复杂度】O(1)
5. 希尔排序与插入排序比较
我们可以使用事后分析法对希尔排序和插入排序做性能比较。
测试从100000 ~ 1的逆向数据数组，我们可以根据执行时间来完成测试。
【执行时间】
希尔排序：29ms
直接插入排序：76826ms
折半插入排序：13075ms
可以看出，希尔排序的效率相比其他两种效率很高。这就是得益于每趟对数组进行的粗略调整。
