import java.util.Arrays;

/**
 * 希尔排序
 */
public class Sort6{
	public static void sort(int[] A){
		int grap = A.length/2;
		while(grap>0){
			System.out.println("grap:"+grap+"   ");
			//i指向每组第一个元素
			for(int i=0;i<grap;i++){
				//对每组进行插入排序
				//j指向每组第二个元素至末尾,假设第一个元素是有序的
				for(int j=i+grap;j<=i+(A.length/grap-1)*grap;j=j+grap){
					//对A[k]进行插入排序
					for(int k=j;k>i;k=k-grap){
						if(A[k]<A[k-grap]){
							Swap.swap(A,k,k-grap);
						}
					}
				}
			}
			System.out.println("Stage :"+Arrays.toString(A));
			grap = grap/2;
		}
	}
}