import java.util.*;

public class ShellSort {

    public int[] shellSort(int[] A, int n) {

        int i, step; //i标识每一组，step标识步长

        for(step = n / 2; step > 0; step /= 2){ //起始的步长为数组长度的一半

            for(i = step; i < n; i++){ //当前步长为step,开始插入排序

                if(A[i] < A[i-step]){ //每个元素与自己组内的数据进行直接插入排序 

                    int target = A[i];

                    int j = i; //j指示当前这一组遍历到哪一个元素

                    while(j>0 && A[j-step] > target){

                        A[j] = A[j-step]; //将j-step位置上的元素移到位置j

                        j -= step;

                        if(j-step < 0)//如果j=1,step=3,没有这个if的话，就会数组越界

                            break;

                    }

                    A[j] = target;

                }

            }

        }

        return A;

    }

}