/// <summary>
    /// 希尔排序
    /// </summary>
    class ArraySh
    {
        private int[] theArray;
        private int nElems;
        public ArraySh(int max)
        {
            theArray = new int[max];
            nElems = 0;
        }
        public void Insert(int value)
        {
            theArray[nElems++] = value;
        }
        public void ShellSort()
        {
            int inner, outer;
            int temp;

            int h = 1;//计算间隔
            while (h <= nElems / 3)
                h = h * 3 + 1;

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