C#如何實現歸并排序

這篇文章主要介紹“C#如何實現歸并排序”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C#如何實現歸并排序”文章能幫助大家解決問題。

什么是歸并？即將兩個有序的數組歸并成一個更大的有序數組。

什么是歸并排序？先將要排序的數組遞歸地分成兩半分別排序，然后將結果歸并起來。

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

1.原地歸并的抽象

實現歸并的一種直截了當的方法是，創建一個適當大小的數組然后將兩個輸入數組中的元素從小到大放入這個數組。因為會多次歸并，防止每次歸并時都創建一個數組，創建數組要放在遞歸的外面。

而原地歸并可以在數組移動元素而不需要使用額外的空間，但是實現非常復雜。下面的歸并方法是非原地歸并：

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

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

            /*
             * 一開始拿左邊部分和右邊部分比較，哪邊小就將小的值一次放入數組 a,并將小的索引 + 1
             *      表示拿下一個和另一部分比較
             * 當某一部分取完時，取另一部分循環放入數組
             * */
            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] 復制到 aux[],即第一個循環。然后開始歸并（第二個循環），拿左邊部分和右邊部分比較，哪邊小就將小的值一次放入數組 a,并將小的索引 + 1。當某一部分取完時，取另一部分循環放入數組。

2.自頂而下的歸并排序

下面的算法通過上面的 Merge 方法實現了自頂而下的歸并排序，這個算法設計使用了分治思想。要對a[lo ... hi] 排序，先將它分為 a[lo ... mid] 和 a[mid+1 ... hi] 兩部分，分別通過遞歸調用單獨對它們排序，最后將有序的子數組歸并為最終的結果。

    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;
        }

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


            //歸并排序后的兩部分
            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; //右邊部分索引

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

            /*
             * 一開始拿左邊部分和右邊部分比較，哪邊小就將小的值一次放入數組 a,并將小的索引 + 1
             *      表示拿下一個和另一部分比較
             * 當某一部分取完時，取另一部分循環放入數組
             * */
            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() 方法會調用自己將 a[0...7] 排序，再在其中調用自己將 a[0...3] 和 a[0...1] 排序。在將 a[0] 和 a[1] 分別排序之后，才會開始將a[0] 和 a[1] 歸并。第二次歸并是a[2] 和 a[3] ，一次類推。

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

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

每一層最多需要 6*N 次訪問數組，2N 次用來復制數組（讀和寫），2N 次用來將排好序的元素移動回去，另外最多比較 2N 次（應該最多N+1次），總共最多訪問數組 6NlogN 次。

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

改進

1. 對于小規模數組，遞歸會使小規模問題中方法的調用過于頻繁，可以在處理小規模問題時使用插入排序。一般可以將歸并排序的運行時間縮短 10% 左右。

2. 在調用 Merge 之前可以增加判斷 ，如果 a[mid] 小于 a[mid+1] ，說明數組已經有序了不需要Merge 。這個改動不影響排序的調用，但是對于有序的子數組算法的運行時間就變成線性了。

3.不將元素復制到輔助數組，可以節省將數組復制到輔助數組的時間。需要調用兩種排序方法：一種將數據從輸入數組排序到輔助數組，另一種將數據從輔助數組排序到輸入數組。（待確認）

3.自底向上的歸并排序

自頂而下的歸并排序是將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題。

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

    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，進行兩兩歸并,歸并次數 N/2^1  ；sz = 2,四四歸并,歸并次數 N/2^2...
             * 要注意檢查是否超出索引，N 不一定是 sz 的倍數
             * */
            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;
        }
    }

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

當數組長度是 2 的冪時，自頂向下和自底向上的歸并排序所用的比較次數和數組訪問次數正好相同，只是順序不同。其他情況可能會有所不同。

自底向上的歸并排序比較適合用鏈表組織的數據。因為鏈表可以原地排序，不需要額外的空間。

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

關于“C#如何實現歸并排序”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。