並べ替えシリーズ(四)---ヒル並べ替え

//author:lilywangcn


public class ShellSort {
	private static int[] array=new int[]{10,30,20,4, 9,-1,6,15,12,8,0,20,4};
	public static void main(String[] args){
		print();
		for(int gap=array.length/2; gap>0; gap/=2){
			System.out.println("gap="+gap);
			for(int i=0;i<gap;i++){
				insertosrt(i,gap);
			}
			print();
		}
	//	print();
	}
	
	private static void insertosrt(int i,int gap){
		for(int j=1;i+gap*j<array.length;j++){
			int tmp=array[i+gap*j];
			int k=j-1;
			while(k>=0&& i+gap*k>=0 &&array[i+gap*k]>tmp  ){
				array[i+gap*(k+1)]=array[i+gap*k];
	//			print();
				k--;
			}
			array[i+gap*(k+1)]=tmp;
	//		print();
		}
	}
	
	private static void print(){
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+" ");
		}
		System.out.println("");
	}
}

アルゴリズム複雑度:O(n*n)、アルゴリズム不安定
実行結果:
 
10 30 20 4 9 -1 6 15 12 8 0 20 4 
gap=6
4 15 12 4 0 -1 6 30 20 8 9 20 10 
gap=3
4 0 -1 4 9 12 6 15 20 8 30 20 10 
gap=1
-1 0 4 4 6 8 9 10 12 15 20 20 30