希尔排序
希尔排序是一种基于插入排序的排序算法。对于大规模的乱序数组，插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点从数组的一端移动到另一端。希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为“h有序数组”。换句话说，一个h有序数组就是h个相互独立的有序数组编织在一起组成的一个数组。在进行排序时，如果h很大，就能将元素移动到很远的地方，为实现更小的h有序创造方便。
1 public static void sort(Comparable[] a) {
2 //将a按升序排列
3 int L = a.length;
4 int h = 1;
5 while (h < L / 3) {
6 h = 3 * h + 1;
7 }
8 while (h >= 1) {
9 //将数组变为h有序
10 for (int i = h; i < L; i++) {
11 for (int j = i; j >= h && (a[j].compareTo(a[j - h]) < 0); j -= h) {
12 Selection.exch(a, j, j - h);
13 }
14 }
15 h = h / 3;
16 }
17
18 }
增量：
在上面这段代码中，使用了序列1/2(3k-1)，从N/3开始递减至1，这个序列叫递增序列。
在希尔排序中，最常用的递增序列是希尔增量（N/2），这个最常用但不是最好的。最坏的情况时间复杂度仍为O(n²)。Hibbard增量序列（2k−1），最坏时间复杂度为O(N3/2)，平均时间复杂度为O(N5/4)；Knuth增量序列 1/2(3k-1)。
实现希尔排序的一种方法是对于每个h，用插入排序将h个子数组独立的排序，但因为子数组是相互独立的，一个更简单的方法是在h到子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格）。只需要在插入排序的代码中将移动元素的距离由1改为h即可。
希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序初，各个子数组都很短，排序后子数组都是部分有序，这两种情况都很适合插入排序。
结论： 希尔排序比插入排序和选择排序更高效，并且数组越大，优势越大。且代码量小，不需要使用额外的内存空间。