效率：O(n*logN)

package sort;

import utils.Util;

/**
 * 希尔排序
 *  以h为间隔，进行比較。 按一定公式。先求出最大的间隔h
 *  当h值大时，须要移动的元素个数就少，但移动的距离长。 内部以h步长的元素做插入排序
 *  当h减小时。每趟排序须要移动的元素个数增多。但此时已接近于它们排序后的终于位置。这对于插入排序更有效率
 * 
 * @author stone
 * @date   2015-7-22 下午4:39:41
 */
public class ShellSort {
	
	
	public static void main(String[] args) {

//		int[] ary = Util.generateIntArray(10);
		int[] ary = {7, 1, 3, 6, 4, 5, 2, 0};
		Util.printArray(ary);
		sort(ary);
		Util.printArray(ary);
	}

	static void sort(int[] ary) {
		int h = 1;
		while (ary.length/3 > h) {
			h = 3 * h + 1;
		}
		while (h > 0) {
			int j, temp;
			for (int i = h; i < ary.length; i++) {
				temp = ary[i];
//				j = i;
//				while (j > h - 1 && ary[j - h] >= temp) {
//					ary[j] = ary[j - h];
//					j -= h;
//				}
				for (j = i; j > h - 1 && ary[j - h] >= temp; j -= h) {
					ary[j] = ary[j - h];
				}
				ary[j] = temp;
//				System.out.println("移动---------");
//				Util.printArray(ary);
			}
			h = (h - 1) / 3;
		}
		
	}
	/*
	 * [7, 1, 3, 6, 4, 5, 2, 0]
	 * h=4 
	 * temp = ary[4], i = 4
	 *  1: [0] 比 [4]   [0]>[4]   [4]=[0]   [0] = temp
	 *  2: temp=ary[5]  [1] 比 [5] 不变     
	 *  3: temp=ary[6]  [2] 比 [6] 变化   [6]=[2]   [2]=temp
	 *  4: temp=ary[7]  [3] 比 [7] 变化   [7]=[3]   [3]=temp
	 *  如今：
	 *  [4, 1, 2, 0, 7, 5, 3, 6] 
	 *      
	 *  [1, 4, 2, 0, 7, 5, 3, 6]  1  移位次数
	 *  [1, 2, 4, 0, 7, 5, 3, 6]  1
	 *  [0, 1, 2, 4, 7, 5, 3, 6]  3
	 *  [0, 1, 2, 4, 7, 5, 3, 6]  
	 *  [0, 1, 2, 4, 5, 7, 3, 6]  1
	 *  [0, 1, 2, 3, 4, 5, 7, 6]  3
	 *  [0, 1, 2, 3, 4, 5, 6, 7]  1
	 *  
	 *  以h为间隔， 按一定公式，先求出最大的间隔h
	 *  while(h>0) {
	 *  	for(i=h;i<len;i++) {
	 *  		for(循环比較[h]和[i-h]的值，并移位)
	 *  	}
	 *  	h = 。。
。 最后一轮时 h=1. 这时  i=n   i比(i-1),(i-1)再比((i-1)-1)  从后向前相邻两个相比
	 *  }
	 */
}