浙江大學-數據結構-歸併排序-9.4.2

03-06

遞歸演算法

分而治之

歸併演算法在談到具體實現的時候，它其實有兩種不一樣的實現策略，那我們先從比較容易理解的遞歸演算法開始介紹，歸併排序的遞歸演算法就是非常典型的分而治之的策略的應用，什麼是分而治之呢？我們其實之前也討論過，就是假設我們待排的序列，是放在這樣的一個數組裡頭，所謂分呢，就是把它一分為二，

然後呢，我就遞歸的去考慮問題，我遞歸的去把左邊排好序，我再遞歸的去把右邊排好序，這樣我就得到了兩個有序的子序列，而且它們肩並肩的放在一起，最後一步呢，調用我們前面核心的歸併演算法，然後把它歸併到一個完整的數組裡面去，

這就是分而治之的典型應用

這個演算法的偽代碼實現呢，也是非常簡單，然後注意到我們這頭又傳進來一堆參數，A是原始待排的數組，然後另外呢，我們仍然是傳進來一個臨時的數組TmpA,這個L指的是什麼呢？L值得是這個位置，就是當前待排的這個序列最左邊的這個位置

RightEnd指的是當前待排序列最右邊的位置，然後我需要一個變數center來記錄它中間的位置，因為我要從中間把它一分為二嘛，當某種條件滿足的時候，

一會我們再說什麼條件滿足的時候啊，我們計算了一個終點的位置，然後我就去遞歸的去把從L到Center的左半邊做了一個遞歸的排序，然後接著把Center+1,一直到RightEnd這個右半邊就遞歸的做了一個排序，兩邊都排好序了以後，調用我剛才的Merge，調用Merge傳進去的是什麼？一個是原始數組A,一個是臨時數組TmpA,還有一個是左邊的起始點L,右邊的起始點Center+1,右邊的終點RightEnd,我們就完成了整個的排序，這個排序出來的結果呢，會存在原來的數組A裡面，回過頭來看當什麼條件滿足的時候，我們才做這件事呢？或者說當什麼條件不滿足的時候，我們就不做這件事了呢？其實很簡單，當我們待排的序列裡面有元素的時候，也就是說當L<RightEnd的時候，我們才做這件事情，遞歸到最底層，就是當L==RightEnd的時候，就意味著你要排的這個數組這一部分就只剩一個元素了，那就什麼都不用排，我直接返回去就好了，那我們對於那些用分而治之的策略來執行的演算法做時間複雜度的分析，也不是第一次了，那這是一個老套路，就是說假設我們解決整個問題，用的時間是T(N)的話，那麼我們遞歸的去解決左半邊用的時間，就一定是T(N/2),因為數據的規模減了一半，那遞歸的去解決右半邊用的時間呢，也是T(N/2),然後我們還需要執行一步，就是一個Merge,就是一步的歸併，這一步歸併的時間複雜度，之前我們也分析過了，這是一個O(N)數量級的演算法，於是我們就得到了一個遞推的公式，

然後我怎麼往下推呢？這個我就不重複了，之前我們推過一次了，從這個遞推式我們就可以得到最後的結果，知道T(N) = O(NlogN),那要注意到這個NlogN是非常強的NlogN,它沒有最好時間複雜度，也沒有最壞時間複雜度，也沒有平均時間複雜度，任何情況下，它都是O(NlogN)的，另外歸併排序還有一個非常好的性質，它是一個穩定的演算法，

那這個演算法到這我們是不是就說完了呢？等一下，還沒有完，我們在最開始的時候，有一個約定，我們在討論任何排序演算法的時候，它都有一個統一的介面，要叫什麼什麼sort,然後它傳進來的參數，不能是這麼一堆亂七八糟的東西，它傳進來的參數只能是原始的數組A加上這個數組裡面元素的個數N,所以這個MSort函數是不滿足這個條件的，於是呢，當用戶在調用一個排序演算法的時候，它會發現你這個很不友好，你必須要給它一個非常友好的統一的函數介面，那這個介面要怎麼做呢？

首先我們得把它寫成一個Merge_Sort就是歸併排序，然後傳進來的參數就是原始的數組A,以及元素的個數N,那我們要記得在之前我們不管是Merge這個函數還是MSort這個函數，我們都始終都帶了一個TmpA，那這個臨時數組是在哪裡申明的呢？就是在介面函數裡面申明的，在這我根據N的大小，申明了一個跟它同等大小的臨時的數組，如果這個空間能申請的到的話，那麼我接著往下做，否則的話，我要跳出來說空間不夠了，如果我可以順利申請到空間的話，我們就調用核心的MSort函數，那MSort函數初始的時候，我要給這兩個參數什麼值呢？這兩個參數是什麼？一個是待排序列最左邊的位置，一個是待排序列最右邊的位置，所以最開始的時候，我們應該傳進去的是從0到N-1,

那最後作為一個專業的，習慣良好的程序員，我們不要忘了，把臨時數組的空間給釋放掉，

在這呢，我不知道你有沒有對一個問題感到很疑惑，就是為什麼我這個MSort要一直帶著TmpA呢？在整個程序的執行過程中，我在什麼地方才真正用到了TmpA呢？其實我在MSort裡面它只是一個遞歸的調用，真正用到TmpA是在Merge,我們核心的歸併函數裡面，才用到這個TmpA的，為什麼這個TmpA要在最外面的這個函數申明，然後每一次都把它作為一個參數往裡傳，看上去很啰嗦的樣子，為什麼我們不直接在Merge函數的內部去申明這個TmpA呢？那我們要仔細的看一下這個TmpA是怎麼用的，一開始的時候，我們有這樣的一個數組，然後我們在Merge_sort裡面剛一進去的時候就申明了另外一個等長的數組，

然後我進入了這個MSort,把這個問題一分為二，你就開始遞歸的解決這個問題，

然後繼續遞歸，然後繼續遞歸

那麼在遞歸的過程中間，我實際上用到了，比如說我在解決這個子問題的時候，

上圖黑色部分最左邊，我用到的是這個數組的哪一段呢？

我實際上是把中間的那個結果通過Merge函數把它歸併到了臨時數組的這一段(綠色部分),然後再把這一段的內容導回到這個A裡面去，然後繼續遞歸的解決這一半

那也是用到臨時數組的這一段，然後再把這一段導回去，然後再把這兩段東西歸併的放在臨時數組的這一塊，

然後再把這一塊的內容導上去，我們從始至終都在同一個數組的某一段上面，反反覆復的做這件事情，從頭到尾，我這個malloc只調用了一次，然後整個程序執行完了以後，這個free也只執行了一次，

如果我不這麼做，會怎麼樣呢？如果我只在Merge中間，聲明一個臨時數組，Merge函數的介面就可以寫的更簡單一點，

MSort這個介面也寫的更簡單一點，那個臨時數組就不出現在傳遞的參數裡頭了，我只有在做Merge的時候才會去申明一個，如果我這麼做的話，在執行程序的時候，你的機器到底在發生什麼事情呢？這是我的初始狀態，然後我把問題一分為二，

然後繼續一分為二

繼續一分為二，

再繼續一分為二，假設說這已經是我分到的最小的單元了，

我在MSort裡面執行了一次Merge,我在執行Merge的時候，臨時開了這麼一個數組，

開完了以後，折騰了一下，我把它給free掉了，然後我去遞歸的解決這一段

解決這一段的時候，我又申明了這麼樣的一個數組，執行完了以後，又把它free掉，然後再退回這一層遞歸的時候呢(黑色部分),我又在merge裡面臨時申明了這麼長的一個數組，我需要把這兩段歸併進來，然後做完了以後，又把它free掉，然後遞歸的去解決右邊

在這兩段都執行完了以後呢，在這個遞歸程序裡面又要開這樣的臨時數組，

於是同樣的我要去解決這邊的問題

解決完了這兩個問題以後呢，我又要去開這樣的臨時數組

同樣的方法去解決另外一半

然後最後呢，還是要開一個大的數組，

去把這兩邊的元素歸併到這個數組裡面，然後再把這個數組裡面的東西再導回去，所以我們看到我們額外的空間複雜度，如果我每一次都記著去釋放空間的話，那麼額外空間複雜度呢倒是O(n)這個數量級的，但是你要看看我們malloc,free了多少次，這麼做實際上是不合算的，最合算的做法呢，就是在一開始的時候，就聲明一個數組，然後每一次呢，都是把這個數組的指針傳進去，然後只在這個數組的某一段上面做操作，就不需要重複的malloc和free了。