前言
希尔排序是基于插入排序实现的（如果不了解插入排序，可以先阅读这篇文章）
一、插入排序的缺点
假设数据中最小的数排在靠右端位置上，这本来是较大值的数据所在位置，把这个小数据移动到左边位置上，所有的中间数据项都必须向右移动一位。
这个步骤对每一个数据项都执行了将近N次的复制。（虽然不是所有数据项都必须移动N个位置，但是数据项平均移动了N/2位置）执行N次N/2个位移，总共是次复制。因此，插入排序的执行效率是
因此如果能以某种方式不必一个一个的移动所有中间数据项，就能把较小的数据项移动到左边，那么这个算法的执行效率就会有很大改进。
二、希尔排序
希尔排序通过加大插入排序中元素之间的间隔，并在这些间隔的元素中进行插入排序，从而使数据能大跨度移动。当这些数据排过一趟之后，希尔排序算法减小数据项的间隔再进行排序。进行排序时数据项之间的间隔被称为增量，用字母h来表示。
下图为增量为4是对包含10个数据项的数据进行排序的过程。
当对7、2、4数据项完成排序之后，算法向右移一步，对10、5、3号数据进行排序。直到所有的数据项都完成了4-增量排序。也就是说所有间隔为4的数据项之间都已经排列有序。
上述例子中，完成以4位增量的希尔排序之后，所有元素离它最终有序的位置相差不到两个单元。这也是希尔排序的奥秘所在。通过创建这种交错的内部有序的数据集合，把完成排序所必须的工作量将到最小。
三、 寻找间隔
上面展示了以4位初始间隔，对10个数据项的数组进行排序。但对于不同长度的数据，如何定义初始间隔，然后不断减小间隔，直到间隔变成1表示排序完成.
这里我们使用公式 以逆向形式从1开始，来查找初始间隔。（这是由Knuth提出的）下面以1000长度的数据项为例
| h | 3*h+1 | (h-1)/3 |
|---|---|---|
| 1 | 4 | |
| 4 | 13 | 1 |
| 13 | 40 | 4 |
| 40 | 121 | 13 |
| 121 | 364 | 40 |
| 364 | 1093 | 121 |
| 1093 | 3280 | 364 |
h值最初为1，然后应用公式h=3*h+1生成序列1,4，13,40,121,364等等。当间隔大于数组长度时停止。对于1000个数据项的数据，1093太大了。因此用364作增量排序。然后，每完成一次排序，就用前面的公式倒推减小间隔：
当数组用1增量排序之后，算法结束。
四、java实现
public class ShellSort {
private int[] arr;
public ShellSort(int[] arr) {
this.arr = arr;
}
public void shellSort() {
int left, right;
int temp;
int h = 1;
//计算初始增量
while (h <= arr.length / 3) {
h = h * 3 + 1;
}
System.out.println("h: "+ h);
while (h > 0) {
for (right = h; right < arr.length; right++) {
temp = arr[right];
left = right;
while (left > h-1 && arr[left - h] >= temp) {
arr[left] = arr[left - h];
left-=h;
}
arr[left] = temp;
}
// System.out.println(Arrays.toString(arr));
//倒推增量
h = (h-1)/3;
}
}
}
五、总结
对比插入排序代码可以看出，插入排序与希尔排序的差别就是增加了一个增量h，但是效率却提高了很多。希尔排序效率大概在O(N^(3/2)) ~O(N^(7/6))之间。
