public class Shell: BaseSort
    {
        public static long usedTimes = 0;
        public Shell()
        {
        }

        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();
            int n = a.Length;
            int h = 1;
            while (h < n / 3)
                h = h * 3 + 1;

            /*
             * 每次循環(huán)生成 h有序數(shù)組（h 個(gè)有序數(shù)組） 即 （h 0）, （h+1 1）, （h+2 2）, ....
             *      如果右邊的值小于左邊的值時(shí)，交換；
             *      并退回到左邊的位置，重新排序，循環(huán)比較（j>=h）。
             *      因?yàn)榻粨Q可能引起原有序的數(shù)組亂序，所以需要退回去重新比較
             * 當(dāng) h 遞減到 1時(shí)，相當(dāng)于插入排序一個(gè)部分有序數(shù)組
             * */
            while (h >= 1)
            {
                //Console.WriteLine(h);
                for (int i = h; i < n; i++)
                {
                    //Console.WriteLine(i+","+(i - h));
                    for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
                    {
                        Exch(a,j,j-h);
                        //Console.WriteLine("J:" + (j- h));
                    }
                }
                h = h / 3;
            }

            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }
    }