排序－希尔

插入排序 对基本有序的数组效果非常好，但是对于通常情况则表现一般。假设最小的数字在最右边，升序排序时，这个数则要经过n次交换比较换到最左边。希尔排序则是对插入排序的很好的修正。而且在希尔排序很少出现最坏状况。

希尔排序通过对数组 以一定间隔相隔的位置 进行插入排序，以达到让数据快速出现在它应该出现的位置的周围，使数组逐步接近基本有序。随着间隔的减少，数组越来越接近基本有序，最后间隔为1时，变成标准的插入排序。

数据的间隔有多种算法，一般要求间隔序列之间互质，此处使用Kunth序列：h = h * 3 + 1

希尔排序的时间效率很难从理论上证明，实验表明大约是O(n^(3/2)) ~ O(n^(7/6))之间。

代码如下：

class Shell {
	public static void main(String[] args) {
		int[] a = {9,8,7,6,5,4,3,2,1};
		sort(a);
		println(a);
	}

	private static void println(int[] a) {
		for(int i: a) System.out.print(i + " ");
		System.out.println();
	}

	private static void sort(int[] a) {
		int h = 1;
		while(h <= a.length/3) h = h * 3 + 1;	//产成Kunth序列
		while(h > 0) {
			for(int i = h; i < a.length; i++) {	//对每个数据进行间隔为h的插入排序
					int pos = i;
					int temp = a[i];
					while(pos >= h && a[pos - h] > temp) {
						a[pos] = a[pos-h];
						pos -= h;
					}
					a[pos] = temp;
			}
			h = (h - 1) / 3;	//减小间隔值
		}
	}
}