C#如何實(shí)現(xiàn)希爾排序

本篇內(nèi)容主要講解“C#如何實(shí)現(xiàn)希爾排序”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“C#如何實(shí)現(xiàn)希爾排序”吧!

對(duì)于大規(guī)模亂序的數(shù)組，插入排序很慢，因?yàn)樗粫?huì)交換相鄰的元素，因此元素只能一點(diǎn)一點(diǎn)地從數(shù)組地一段移動(dòng)到另一端。希爾排序改進(jìn)了插入排序，交換不相鄰地元素以對(duì)數(shù)組地局部進(jìn)行排序，最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。

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

在進(jìn)行排序時(shí)，剛開(kāi)始 h 很大，就能將元素移動(dòng)到很遠(yuǎn)的地方，為實(shí)現(xiàn)更小的 h 有序創(chuàng)造方便。h 遞減到 1 時(shí)，相當(dāng)于插入排序。這就是希爾排序。下面的代碼 h 從 N/3 開(kāi)始遞減，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;

            /*
             * 每次循環(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;
        }
    }

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

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

• 和選擇排序以及插入排序?qū)Ρ?，希爾排序也可以用于大型?shù)組，即使是隨機(jī)數(shù)字排序也快很多。數(shù)組規(guī)模越大，對(duì)比越明顯。

• 希爾排序的性能分析比較困難。它的運(yùn)行時(shí)間達(dá)不到平方級(jí)別，在最壞情況下的比較次數(shù)和  N ^ 3/2 成正比。

• 如果中等大小的數(shù)組可以使用希爾排序，它代碼量少，且不需要額外的內(nèi)存空間。

百萬(wàn)級(jí)別的排序時(shí)間不超過(guò)十秒：

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

到此，相信大家對(duì)“C#如何實(shí)現(xiàn)希爾排序”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！