算法--希尔排序

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要 N-1 次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

基本思想：
先取一个小于数组长度n的整数h作为第一个增量，把数组的全部元素分组。所有距离为h的倍数的元素放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量h（小于第一个增量h）重复上述的分组和排序，直至所取的增量h=1，即所有元素放在同一组中进行直接插入排序为止。

该方法实质上是基于插入算法的一种分组插入方法。

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。

D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量h分成若干组，每组中元素的下标相差h.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

算法的性能与h的选择有关，但是h的选择仍然是数学的前沿研究问题，没有定论，我们只能根据我们的经验和需要来选取适合的h。

稳定性：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

复杂度：
希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(n的3/2次方)，希尔排序时间复杂度的下界是n*log2n。
空间复杂度为O（1）。

代码实现：

public class Test {
	public static void sort(int[] numbers) {
		int l = numbers.length;
		int h = 1;
		int count = 0;
		while (h < l/3) h = h*3+1;//确定有序子数组的个数h
		while (h >= 1) {
			count++;
			for (int i = h;i < l;i++) {
				for (int j = i;j >= h;j -= h) {
					if ((numbers[j] < numbers[j-h])){
						int temp = numbers[j];
						numbers[j] = numbers[j-h];
						numbers[j-h] = temp;
					}
				}
			}
			System.out.println("第" + count + "趟排序");
			System.out.println(Arrays.toString(numbers));
			h = h/3;//重新选取h
		}
	}
	
	public static void main(String[] args) {
		int[] numbers = {1,5,9,8,7,2,3,5,4,0};
		System.out.println("排序前：");
		System.out.println(Arrays.toString(numbers));
		sort(numbers);
	}
}

运行结果：