希尔排序算法因科学家 Donald L. Shell 得名， 它是基于插入排序的， 但增加了一个特性，即增量排序，它在有间隔的元素中进行插入排序，然后减小间隔，直到为间隔1。 比如说先对下标为0,4.8的元素进行排序，然后对下标为 1,5,9的元素排序，接下来减小间隔， 如对 0,1 排序。
插入排序对基本有序的数组排序效率非常高，然而通常情况下， 如果有小的元素在最后， 则它几乎要移动 N 个位置才能来到前面， 平均也要 N/2 次，对于 N 个数来说， 移动的次数太多了。希尔排序使用增量，让元素可以大跨度地移动， 而不是一个一个地往前移， 那么经过很少次数的移动后， 数组会变成若干个小的基本有序的数组，到最后增量减为1的时候， 每个元素离自己的正确位置不过一两步而已。事实上在最后一步，增量减为1的时候，就是一个普通的插入排序了。刚开始对希尔排序可能不太理解， 但如果将插入排序看作是增量始终为1的希尔排序，则问题就迎刃而解。
增量的大小对效率的影响非常之大， 可能算法不仅是一种， 但通常认为， 增量序列应该是互质的， 且无论如何，最后都要保证增量的值为1。 Donald E. Knuth 的算法是 h = 3*h +1. 由于这些因素，它的时间复杂度通常在 O(N^2/3) ~ O(N^6/7) 之间。 按最坏的情况算， 接近于O(N^2/3).
代码片断
/*
based on insert sort, but use a increment value
between elements, the elements are not compared
and swaped with the one just next to them, but
the ones that have a distance between them, the
distance is decided by the value of increment.
*/
public void sort () {
int h = 1; //设定增量的初始值
// 因为增量不能大小数组的长度，所以 3h+1 <= maxSize
while (h <= (maxSize-1)/3) {
h = 3*h+1; // 按公式得到最大的增量，也即第一个要用的增量
}
while (h > 0) { // 增量减到1的时候是最后一次了
for (int i = h; i<maxSize; i++)
int tmp = array[i]; // 与插入排序相同
// 从当前元素开始，以一个增量为单位向前跳，直到自己开始的地方为止
int j = i;
while ( j>h-1 && array[j-h] >= tmp) {
// 如果这个元素比自已大，就往后移动一个增量
array[j] = array[j-h];
j = j - h; // 每次递减一个增量
}
if ( j != i ) {
array[j] = tmp; // 找到了位置就插入
}
} // END WHILE
h = (h-1) / 3; // 减小增量值, 由 h = 3h+1 反推而得
} // END FOR
}