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

歸併排序

核心：有序子列的歸併

我們來看個例子吧，假設我們有兩個子序列，這兩個子序列本身已經是排好序的，那我們的目標是開另外一個數組，然後要把這些數字一個一個的放到這個數組裡面去

然後希望最後這個數組是從小到大有序的，那我們要怎麼做呢？其實這個演算法很簡單，在之前的課程中講線性表的時候，兩個多項式是怎麼相加的呢？其實這個想法是非常相似的，我們先要準備好3個指針，

A指針指向A序列的當前的第一個元素，B指針指向B序列當前第一個元素，C指針指向現在你要放的這個元素的位置，有一點需要特彆強調說明的是，當我們在說到一個指針的時候，它不一定真是C語言裡頭說的那個語法上的指針，所謂指針它本職就是它存的是位置，如果我們在討論的是一個數組，那麼數組元素的位置是由它的下標決定的，所以呢，其實我們在這說指針，這個指針可以就是整數，這個整數存的是這個元素的下標，接下來我們要看這件事情要怎麼開始，第一步就是先比一下，這個A指針和B指針指向的兩個元素誰比較小一點，然後把比較小的元素放到C指針指的位置上，做完這件事情以後，因為我改變了A嗎，然後A++,A往前挪，C++往前挪，指到下一個空位，然後繼續比較A指針和B指針的兩個元素，

我們發現2的元素更小一點，於是呢，把這個2放進來，然後B指針加加(B++),C指針加加(C++),

接下來的事情你應該知道怎麼做了，那我們的問題就是如果兩個子列一共有N個元素，那麼這一趟歸併它的時間複雜度是什麼呢？

每一個元素被掃描了一遍，每一個元素被存進來一次，所以顯然它的時間複雜度就是O(N)這個數量級的，

接下來我們就看一下有序子列歸併的偽代碼要怎麼寫，我們把這個函數取個名字叫Merge,就是歸併

那我們注意到傳進來一堆的參數，它們分別是什麼東西呢？這個ElementType A是原始的待排的序列，同時呢，我要傳進來一個TmpA,因為我要歸併的時候，不是要把兩個子列導到另外一個數組裡嗎？所以我需要一個臨時的數組，這個數組也傳進來，這個L指的是我要歸併的左邊的起始位置，也就是剛才我們那個Aptr,R呢，是指的右邊的起始位置，相當於我們剛才的Bptr,我們還需要一個量來存右邊終點位置，也就是右邊這一半最後一個元素所在的位置，那有傳進來的這3個參數以後呢，我們其實可以算出來這個LeftEnd,也就是左邊子列它的終點的位置，那我們在這做了一個假設就是左右兩列是肩並肩挨著的，所以呢，左邊的終點就是右邊起點的前一個位置，就是R-1,那Tmp一開始等於L,它指的是什麼呢？Tmp就相當於我們前面那個圖裡面的Cptr,它指的是在這個臨時數組裡面，它要從哪開始存放歸併完了以後的結果，歸併結果的位置，跟原始數組裡面元素的位置是對著的，所以它也要從第L個開始放，通過傳進來的參數呢，我們可以算出來到底我們歸併完了以後那個元素的總個數是多少，也就是最右邊終點的位置減去最左邊的的位置加1，得到的是整個歸併完以後中間會有多少個元素，上圖都是準備工作，準備工作做完了以後，就開始歸併了，這就是我們的歸併過程

那在歸併過程中間，每一次我們比較左邊位置的元素跟右邊的元素誰更小一點，如果左邊的更小一點的話，那麼我們把左邊的這個放到臨時的TmpA裡面去，然後Tmp++,L++,否則的話呢，說明我們應該把右邊的這個放到數組裡面去，於是我們把A右邊的這個放到臨時數組裡面去，然後Tmp++,R++，循環持續進行的條件是什麼呢？就是當L小於左邊的終點(LeftEnd),並且R小於右邊終點的時候(RightEnd），也就是說當左右兩邊的子序列都不為空的時候，那我們就繼續往下走，一直走到什麼時候跳出來了呢？走到這兩個條件其中之一不滿足的時候，就要跳出來了，就意味著其中一個子序列，已經空了，沒有元素了，而另外一個子序列呢，當然也有可能空了，也可能沒空，那我們就把另外一個序列裡面剩下的元素，全部直接導到這個TmpA裡面就可以了，如果從while循環里跳出來的時候，L還小於等於左邊的終點的時候，那說明左邊的這個數組還有東西剩下來，那我就直接把左邊剩下的導到TmpA里，那如果說右邊的還有剩下的，那我就把右邊剩下的導到TmpA里，雖然我在這寫了兩個while循環(while(L<=LeftEnd)TmpA[Tmp++] = A[L++]; while(R <= RightEnd) TmpA[Tmp++] = A[R++];)，但是實際程序在執行的時候，它只有其中一個while循環會被執行，另外一個是不可能執行的，因為如果兩個條件都滿足的話，它應該還在上面的while循環裡面還沒跳出來呢(while(L <= LeftEnd && R <= RightEnd)),那我們知道TmpA裡面存的就是歸併以後的結果了，光把結果存在TmpA裡面是不行的，還得把TmpA裡面的結果導回到A裡面去，那這個時候呢，要怎麼導呢？你乍一想這件事情不是很簡單嗎？那我只要做一個循環，比如說讓i從L一直循環到RightEnd,然後把所有TmpA導到A裡面去不就好了嗎？等一下，這個L

當我程序執行到這一步的時候，還在嗎？你要注意到我們這L++加到最後的時候，L指到哪去了都不知道，所以呢，這個序列最初是從哪開始的，這個位置，好像已經丟掉了，我不知道前面的起始位置了，我們該怎麼辦呢？聰明一點，我不一定非要從左往右導，我也可以從右往左導，我要注意到RightEnd這個東西好像從頭到尾這個東西是沒有變過的，所以我就可以做這麼一件事情，就是我從RightEnd開始把TmpA往A裡面導回去，然後每一次呢，RightEnd--,但是我要減多少次呢，我一共減這麼多次就可以了(NumElements),這就是為什麼一開始我得把這個元素的總個數得計算出來，然後存在這裡，這只是一個很小的細節處理。