效率：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)  从后向前相邻两个相比

	 *  }

	 */

}