shell排序

public class ShellSort {

	public static void main(String[] args) {

		int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
		print(data);
		shellSort(data, data.length);
		print(data);
	}

    /**
    	shell排序的实现算法，原理就是使用不同的增量进行分组，之后对每个分组进行插入排序
    */
	public static void shellSort(int[] array, int n) {
		int gap, i, j;
		//使用增量分割子序列，这里的gap就是增量，使用增量对数组进行分割
		for (gap = n / 2; gap > 0; gap /= 2)

		{
			// 内层的两个循环对每一个子序列同时做直接插入排序
			for (i = gap; i < n; i++){
				int insertNode=array[i];  //待插入的数据
				j=i-gap;   //待插入数据的前一个下标
				
				//循环结束的条件是insertNode>=array[j],那么此时的insertNode需要插入的位置就是array[j+1]这个位置了
				while(j>=0&&insertNode<array[j]){
					array[j+gap]=array[j];   //元素后移
					j=j-gap;
				}
				array[j+gap]=insertNode;   //此时的array[j+gap]就是待插入的位置
			}
		}
	}

	public static void print(int[] data) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
}