快捷導(dǎo)航

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

更新時(shí)間：2022年04月15日 13:56:44 作者：Ruby_Lu

這篇文章介紹了C#實(shí)現(xiàn)歸并排序的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

什么是歸并？即將兩個(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] ，一次類推。

用每個(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ù)組（讀和寫），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;
        }
    }