希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。 该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

public class ShellSorting {	static void sort(int[] a) {		if (a == null || a.length == 0) {			return;		}		int k = a.length >> 1;		while (k >= 1) {			for (int i = 0; i < k; i ++) {				insertionSort(a, i, k);			}			k >>= 1;		}	}	/**	 * 	 * insertionSort: 直观的希尔排序	 * 	 * @param a	 * @param start	 * @param incre	 */	static void insertionSort(int[] a, int start, int incre) {		for (int i = start + incre; i < a.length; i += incre) {			if (a[i] < a[i - incre]) {				int x = a[i];				int j = i - incre;				while (j >= 0 && x < a[j]) {					a[j + incre] = a[j];					j -= incre;				}				a[j + incre] = x;			}		}	}	}

很明显，上面的shellsort代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。

public class AdvancedShellSorting {	static void sort(int[] a) {		if (a == null || a.length == 0) {			return;		}		int k = a.length >> 1;		while (k >= 1) {			insertionSort(a, k);			k >>= 1;		}	}	/**	 * 	 * insertionSort: 优化的希尔排序	 * 	 * @param a	 * @param start	 * @param incre	 */	static void insertionSort(int[] a, int incre) {		for (int i = incre; i < a.length; i += 1) {			if (a[i] < a[i - incre]) {				int x = a[i];				int j = i - incre;				while (j >= 0 && x < a[j]) {					a[j + incre] = a[j];					j -= incre;				}				a[j + incre] = x;			}		}	}}

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

希尔排序