希尔排序
 

  希尔排序：也叫作缩减增量排序，它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而缩小，直到只比较相邻元素的最后一趟排序为止。
  希尔排序使用一个序列h1，h2，...，ht，叫做增量排序，在使用增量ht的一趟排序之后，对于每一个i我们都有a[i] ≤ a[i + ht]，所有相隔ht元素都被排序。此时称文件是ht排序的，如下图显示的是几趟希尔排序后数组的情况：

原始数组
81
94
11
96
12
35
17
95
28
58
41
75
15

5 排序后
35
17
11
28
12
41
75
15
96
58
81
94
95

3 排序后
28
12
11
35
15
41
58
17
94
75
81
96
95

1 排序后
11
12
15
17
28
35
41
58
75
81
94
95
96

  排序的作用就是对hk个独立的子数组执行一次插入排序。增量排序的一个流行的选择是使用Shell建议的序列：ht= N/2和hk = hk+1/2。算法如下：

void shellSort(int[] a){
    int j;
    for(int gap = a.length /2; gap > 0; gap /=2){
        for(int i = gap; i < a.length; i++){
            int temp = a[i];
            for(j = i; j >= gap && temp < a[j - gap]; j-= gap)
                a[j] = a[j - gap];
            a[j] = temp;
        }
    }
}

  希尔排序的最坏情形运行时间为O(N2)。