希尔排序

1、什么是希尔排序？

希尔排序由计算机科学家希尔发现，希尔排序是给予插入排序的一种新的排序方法，较之余传统的插入排序，希尔排序的效率更为高效

2、上源码

public class ArraySh {

	private long[] theArray;
	private int nElems;
	
	public ArraySh(int max) {
		theArray = new long[max];
		nElems = 0;
	}
	
	public void insert(long value) {
		theArray[nElems] = value;
		nElems++;
	}
	
	public void display() {
		System.out.print("A=");
		for(int i = 0; i < nElems; i++) {
			System.out.print(theArray[i] + " ");
		}
		System.out.println(" ");
	}
	
	public void shellSort() {
		int inner, outer;
		long temp;
		int h = 1;
		while(h < nElems/3) {
			h = h*3 +1;
		}
		
		while(h > 0) {
			for(outer = h; outer < nElems; outer++) {
				temp = theArray[outer];
				inner = outer;
				while(inner > h-1 && theArray[inner-h] >= temp) {
					theArray[inner] = theArray[inner-h];
					inner -= h;
				}
				theArray[inner] = temp;
			}
			h = (h-1)/3;
		}
		
	}
	
}

public class ShellSortApp {

	public static void main(String[] args) {
		int maxSize = 10;
		ArraySh arr;
		arr = new ArraySh(maxSize);
		for(int i=0; i<maxSize; i++	) {
			long n = (int) (java.lang.Math.random()*99);
			arr.insert(n);
		}
		arr.display();
		arr.shellSort();
		arr.display();
	}
}

3、运行结果

A=34 97 21 96 84 5 19 66 27 95  
A=5 19 21 27 34 66 84 95 96 97  

4、算法分析

希尔排序的核心算法在于shell.Sort()方法，总体思路是在大范围内使之有序，最后再在小范围内使之有序。

当完成第一次for循环后，h递减，使之在更小的范围内排序，指导h=1的情况，就是整个数组全排序，从而保证了整个数组的有序性

当执行完会h=1的循环后，退出了外层的while循环，算法结束。

Reference：

[1] Robert Lafore(著), 计晓云, 赵研, 曾希, 狄小菡(译), Java数据结构和算法(第二版), 中国电力出版社, 2004:238-245