排序系列（四）---希尔排序

 

//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