C#如何實(shí)現(xiàn)歸并排序

這篇文章主要介紹“C#如何實(shí)現(xiàn)歸并排序”的相關(guān)知識(shí)，小編通過(guò)實(shí)際案例向大家展示操作過(guò)程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“C#如何實(shí)現(xiàn)歸并排序”文章能幫助大家解決問(wèn)題。

什么是歸并？即將兩個(gè)有序的數(shù)組歸并成一個(gè)更大的有序數(shù)組。

什么是歸并排序？先將要排序的數(shù)組遞歸地分成兩半分別排序，然后將結(jié)果歸并起來(lái)。

歸并排序能夠保證將任意大小為 N 的數(shù)組排序所需的時(shí)間和 N logN 成正比；缺點(diǎn)是它所需的額外空間和 N 成正比。

1.原地歸并的抽象

實(shí)現(xiàn)歸并的一種直截了當(dāng)?shù)姆椒ㄊ?，?chuàng)建一個(gè)適當(dāng)大小的數(shù)組然后將兩個(gè)輸入數(shù)組中的元素從小到大放入這個(gè)數(shù)組。因?yàn)闀?huì)多次歸并，防止每次歸并時(shí)都創(chuàng)建一個(gè)數(shù)組，創(chuàng)建數(shù)組要放在遞歸的外面。

而原地歸并可以在數(shù)組移動(dòng)元素而不需要使用額外的空間，但是實(shí)現(xiàn)非常復(fù)雜。下面的歸并方法是非原地歸并：

        public static void Merge(IComparable[] a, int lo, int mid, int hi)
        {
            //Console.WriteLine(lo+","+mid+","+hi);
            
            int i = lo; //左邊部分索引
            int j = mid + 1; //右邊部分索引

            //復(fù)制一份數(shù)組
            for (var k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
                //Count++;
            }

            /*
             * 一開(kāi)始拿左邊部分和右邊部分比較，哪邊小就將小的值一次放入數(shù)組 a,并將小的索引 + 1
             *      表示拿下一個(gè)和另一部分比較
             * 當(dāng)某一部分取完時(shí)，取另一部分循環(huán)放入數(shù)組
             * */
            for (var k = lo; k <= hi; k++)
            {
                if (i > mid)
                    a[k] = aux[j++];
                else if (j > hi)
                    a[k] = aux[i++];
                else if (Less(aux[j], aux[i]))
                    a[k] = aux[j++];
                else
                    a[k] = aux[i++];
            }
        }

Merge 方法先將a[lo ... hi] 復(fù)制到 aux[],即第一個(gè)循環(huán)。然后開(kāi)始?xì)w并（第二個(gè)循環(huán)），拿左邊部分和右邊部分比較，哪邊小就將小的值一次放入數(shù)組 a,并將小的索引 + 1。當(dāng)某一部分取完時(shí)，取另一部分循環(huán)放入數(shù)組。

2.自頂而下的歸并排序

下面的算法通過(guò)上面的 Merge 方法實(shí)現(xiàn)了自頂而下的歸并排序，這個(gè)算法設(shè)計(jì)使用了分治思想。要對(duì)a[lo ... hi] 排序，先將它分為 a[lo ... mid] 和 a[mid+1 ... hi] 兩部分，分別通過(guò)遞歸調(diào)用單獨(dú)對(duì)它們排序，最后將有序的子數(shù)組歸并為最終的結(jié)果。

    public class MergeSort : BaseSort
    {
        public static IComparable[] aux = null;
        public static long usedTimes = 0;
        public MergeSort()
        {
        }

        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();
            aux = new IComparable[a.Length];
            Sort(a, 0,a.Length-1);
            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }

        //將數(shù)組a[lo ... hi]排序
        public static void Sort(IComparable[] a, int lo, int hi)
        {
            //遞歸調(diào)用Sort(IComparable[] a, int lo, int hi)
            if (hi<=lo)
                return;
            int mid = lo + (hi-lo)/2;
            Sort(a,lo,mid);//將左邊部分排序(遞歸調(diào)用)
            Sort(a,mid+1,hi);//將右邊部分排序(遞歸調(diào)用)


            //歸并排序后的兩部分
            Merge(a,lo,mid,hi);
        }
        public static int Count = 0;
        public static void Merge(IComparable[] a, int lo, int mid, int hi)
        {
            //Console.WriteLine(lo+","+mid+","+hi);
            
            int i = lo; //左邊部分索引
            int j = mid + 1; //右邊部分索引

            //復(fù)制一份數(shù)組
            for (var k = lo; k <= hi; k++)
            {
                aux[k] = a[k];
                //Count++;
            }

            /*
             * 一開(kāi)始拿左邊部分和右邊部分比較，哪邊小就將小的值一次放入數(shù)組 a,并將小的索引 + 1
             *      表示拿下一個(gè)和另一部分比較
             * 當(dāng)某一部分取完時(shí)，取另一部分循環(huán)放入數(shù)組
             * */
            for (var k = lo; k <= hi; k++)
            {
                if (i > mid)
                    a[k] = aux[j++];
                else if (j > hi)
                    a[k] = aux[i++];
                else if (Less(aux[j], aux[i]))
                    a[k] = aux[j++];
                else
                    a[k] = aux[i++];
            }
        }
    }

如上軌跡所示，要將 a[1...15] 排序，Sort() 方法會(huì)調(diào)用自己將 a[0...7] 排序，再在其中調(diào)用自己將 a[0...3] 和 a[0...1] 排序。在將 a[0] 和 a[1] 分別排序之后，才會(huì)開(kāi)始將a[0] 和 a[1] 歸并。第二次歸并是a[2] 和 a[3] ，一次類(lèi)推。

用每個(gè)結(jié)點(diǎn)表示一個(gè) Sort() 方法通過(guò)Merge 方法歸并而成的子數(shù)組。這棵樹(shù)正好有 n(n = logN) 層。對(duì)于0 到 n-1 之間的任意 k ，自頂而下的第 k 層有 2^k 個(gè)數(shù)組，每個(gè)數(shù)組的長(zhǎng)度為 2^ n-k，由Merge 方法中比較的代碼可知比較次數(shù)為2^ n-k。因此每層比較次數(shù)為 2^k * 2^n-k = 2^n，n 層總共為 n* 2^n = N logN。

由于并不是每次一分為二子數(shù)組不一定均分，總比較次數(shù)小于等于N logN，大于等于 1/2N logN。

每一層最多需要 6*N 次訪問(wèn)數(shù)組，2N 次用來(lái)復(fù)制數(shù)組（讀和寫(xiě)），2N 次用來(lái)將排好序的元素移動(dòng)回去，另外最多比較 2N 次（應(yīng)該最多N+1次），總共最多訪問(wèn)數(shù)組 6NlogN 次。

由上可知，歸并排序所需的時(shí)間和 NlogN 成正比。主要缺點(diǎn)是需要額外空間和 N 大小成正比。

改進(jìn)

1. 對(duì)于小規(guī)模數(shù)組，遞歸會(huì)使小規(guī)模問(wèn)題中方法的調(diào)用過(guò)于頻繁，可以在處理小規(guī)模問(wèn)題時(shí)使用插入排序。一般可以將歸并排序的運(yùn)行時(shí)間縮短 10% 左右。

2. 在調(diào)用 Merge 之前可以增加判斷 ，如果 a[mid] 小于 a[mid+1] ，說(shuō)明數(shù)組已經(jīng)有序了不需要Merge 。這個(gè)改動(dòng)不影響排序的調(diào)用，但是對(duì)于有序的子數(shù)組算法的運(yùn)行時(shí)間就變成線性了。

3.不將元素復(fù)制到輔助數(shù)組，可以節(jié)省將數(shù)組復(fù)制到輔助數(shù)組的時(shí)間。需要調(diào)用兩種排序方法：一種將數(shù)據(jù)從輸入數(shù)組排序到輔助數(shù)組，另一種將數(shù)據(jù)從輔助數(shù)組排序到輸入數(shù)組。（待確認(rèn)）

3.自底向上的歸并排序

自頂而下的歸并排序是將一個(gè)大問(wèn)題分割成小問(wèn)題分別解決，然后用所有小問(wèn)題的答案來(lái)解決整個(gè)大問(wèn)題。

盡管我們考慮的是歸并兩個(gè)大數(shù)組，實(shí)際上我們歸并的數(shù)組大部分都很小。所以我們可以使用另外一種排序方法自底向上，先歸并那些小數(shù)組，然后再成對(duì)歸并得到的子數(shù)組，最終會(huì)將整個(gè)數(shù)組歸并到一起。先兩兩歸并，然后四四歸并...

    public class MergeSortBu: MergeSort
    {
        //static IComparable[] aux = null;
        public new static long usedTimes = 0;
        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();
            aux = new IComparable[a.Length];
            int n = a.Length;

            /*
             * sz = 1，進(jìn)行兩兩歸并,歸并次數(shù) N/2^1  ；sz = 2,四四歸并,歸并次數(shù) N/2^2...
             * 要注意檢查是否超出索引，N 不一定是 sz 的倍數(shù)
             * */
            for (var sz = 1; sz < n; sz = sz + sz)
            {
                for (int lo = 0; lo < n - sz; lo += sz+sz)
                    Merge(a,lo,lo+sz-1,Math.Min(lo+sz+sz-1,n-1));
            }

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

自底向上歸并排序的比較次數(shù)同樣小于等于N logN，大于等于 1/2N logN。最多訪問(wèn)數(shù)組次數(shù)6NlogN 次。

當(dāng)數(shù)組長(zhǎng)度是 2 的冪時(shí)，自頂向下和自底向上的歸并排序所用的比較次數(shù)和數(shù)組訪問(wèn)次數(shù)正好相同，只是順序不同。其他情況可能會(huì)有所不同。

自底向上的歸并排序比較適合用鏈表組織的數(shù)據(jù)。因?yàn)殒湵砜梢栽嘏判?，不需要額外的空間。

沒(méi)有任何基于比較的算法能夠保證使用少于 lg( N! ) ~ N lg N 次比較將長(zhǎng)度為 N 的數(shù)組排序。

關(guān)于“C#如何實(shí)現(xiàn)歸并排序”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。