学步园

希尔排序的方法：

public void shellSort(){
        int inner,outer;
        long temp;
        int h = 1;

        while(h<=nElems/3){
            h = 3*h+1;
        }

        while(h>0){
            for(outer = h;outer<nElems;outer++){
                inner = outer;
                temp = theArray[outer];
                while(inner>h-1&&theArray[inner-h]>temp){
                    theArray[inner] = theArray[inner-h];
                    inner -=h;
                }
                theArray[inner] = temp;
            }
            h = (h-1)/3;
        }
    }

其中，h是间隔，在这里采取h=3*h+1的间隔函数。

希尔排序的时间复杂度，理论值目前还没有人计算出来，实验值是O(N^3/2)到O(N^7/6)。而冒泡、插入、选择排序的时间复杂度均为O(N²)。

希尔排序用于中等数据量的排序。而间隔函数h,最好是质数。