高级排序-希尔排序

原理

1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2. 对分好组的每一组数据完成插入排序；
3. 减小增长量，最小值为1，重复第二步操作。
   
   增长量h的确定：增长量h的值每一固定的规则，采用以下规则：

int h=1; 
while(h<5) {    
   h=2h+1;//3,7 
}//循环结束后我们就可以确定h的大值； h的减小规则为：    h=h/2

代码示例

public class Shell {
	
	public static void sort(Comparable[] a) {
		//确定增长量
		int N = a.length;
		int h = 1;
		while(h < N / 2) {
			h = h * 2 + 1;
		}
		
		while(h >= 1) {
			for (int i = h; i < N; i++) {
				for (int j = i; j >= h; j-=h) {
					if(greater(a[j - h], a[j])) {
						exch(a, j, j - h);
					} else {
						break;
					}
				}
			}
			h /= 2;
		}
	}
	
	private static boolean greater(Comparable v, Comparable w) {
		return v.compareTo(w) > 0;
	}
	
	private static void exch(Comparable[] a, int i, int j) {
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public static void main(String[] args) {
		Integer[] a = { 45, 7, 85, 6, 2, 0, 19, 33, 1, 8, 10, 22, 41, 79, 18 };
		Shell.sort(a);
		System.out.println(Arrays.toString(a));
	}
}