希爾排序

　　對於大規模亂序的數組，插入排序很慢，因為它只會交換相鄰的元素，因此元素只能一點一點地從數組地一段移動到另一端。希爾排序改進了插入排序，交換不相鄰地元素以對數組地局部進行排序，最終用插入排序將局部有序的數組排序。

　　希爾排序的思想是使數組中任意間隔為 h 的元素都是有序的。這樣的數組成為 h 有序數組。換句話說，一個 h 有序數組就是 h 個相互獨立的有序數組組合在一起的一個數組。

　　　　　　　　

　　在進行排序時，剛開始 h 很大，就能將元素移動到很遠的地方，為實現更小的 h 有序創造方便。h 遞減到 1 時，相當於插入排序。這就是希爾排序。下面的程式碼 h 從 N/3 開始遞減，h = h * 3 + 1:

    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;

            /*
             * 每次循環生成 h有序數組（h 個有序數組） 即 （h 0）, （h+1 1）, （h+2 2）, ....
             *      如果右邊的值小於左邊的值時，交換；
             *      並退回到左邊的位置，重新排序，循環比較（j>=h）。
             *      因為交換可能引起原有序的數組亂序，所以需要退回去重新比較
             * 當 h 遞減到 1時，相當於插入排序一個部分有序數組
             * */
            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;
        }
    }

　　從另一個角度看希爾排序，插入排序是將每個比元素大的元素向右移動一個，希爾排序是交換到比它大的元素之前，移動距離從 1 改成 h 。

　　希爾排序更高效的原因是它將數組變成多個部分有序的數組，減少倒置。排序之初，各個子數組都很短，排序之後子數組都是部分有序的，這很適合插入排序。子數組部分有序的程度取決於遞增序列的選擇。（如何選擇？？）

　　和選擇排序以及插入排序對比，希爾排序也可以用於大型數組，即使是隨機數字排序也快很多。數組規模越大，對比越明顯。

　　希爾排序的性能分析比較困難。它的運行時間達不到平方級別，在最壞情況下的比較次數和  N ^ 3/2 成正比。

　　如果中等大小的數組可以使用希爾排序，它程式碼量少，且不需要額外的記憶體空間。

　　

　　百萬級別的排序時間不超過十秒：

　　count:10000 shell use Milliseconds:6
　　count:100000 shell use Milliseconds:180
　　count:1000000 shell use Milliseconds:3226

Tags:

VirMach 便宜 VPS