希尔排序

        希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

        希尔排序将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如，将n个记录分成d个子序列：

        {R[1],R[1+d],R[1+2d],…,R[1+kd]}

        {R[2],R[2+d],R[2+2d],…,R[2+kd]}

         ……………………………………

        {R[d],R[2d],R[3d],…,R[kd],R[(k+1)d]}

        其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。

        核心代码如下：

public static void shellSort(int[] arr, int[] incre, int t) {		for (int k=0; k<t; ++k) {		// t==incre.length; incre = {5, 3, 1}			shellInsert(arr, incre[k]);		}		System.out.PRintln("希尔排序的结果为：");		for (int i=0; i<arr.length; ++i) {			System.out.print(arr[i] + " ");		}	}		public static void shellInsert(int[] arr, int d) {		// 对以d为增量的序列进行直接插入排序		int j;		for (int i=d; i<arr.length; ++i) {			if (arr[i]<arr[i-d]) {				int temp = arr[i];				for (j=i-d; j>=0&&temp<arr[j]; j-=d)					arr[j+d] = arr[j];				arr[j+d] = temp;			}		}        }
运行结果：
说明：
（1）希尔排序是不稳定的排序方法。
（2）时间复杂度在O(nlog2n)~O(n2)之间，平均O(n1.3)到O(n1.5)。空间复杂度O(1)。