【演算法】歸併排序

• 2020 年 8 月 20 日
• 筆記
• mergesort, 歸併, 歸併排序, 快排, 演算法

目錄結構：

1. 簡介

歸併排序（MergeSort） 和快排的思想有相似之處。都是採用分治的思想，也就是，首先在一個數組中選擇一個基準點，把數組分成兩半，然後再對每一半再進行排序，遞歸直到所有數據都排好序。歸併排序取分割點都是在數組的最中間，而且歸併的過程也是採用了一個額外的數組變數來周轉實現的。

首先先用C語言實現一個歸併排序的過程。

是不是上面的程式碼不太好理解，別擔心，下面筆者製作了一張gif圖片，可以更加形象理解歸併排序的過程。

2. 歸併排序的時間複雜度

上面討論了歸併排序的實現過程和理論基礎，接下來繼續討論歸併排序的時間複雜度。歸併排序和快速排序相似，接下來深入分析一下歸併排序的時間複雜度，由於歸併排序每次取的都是數列最中間的位置，於是我們可以得出如下的表達式：

T(n)  = T(n/2) + T(n/2) + n

這個表達式和快排最優情況下的表達式一樣，這裡我就不再解一遍了，詳情請移步快速排序最優時間複雜度。 解上面表達式最終可以得到時間複雜度為： n logⁿ. 

因為歸併排序總是取的最中間的位置，所以無論排序的數列是什麼樣的，數列的排序都只有一種情況。換句話說，歸併排序的最差，最優，平均時間複雜度都是O(n logⁿ)。

3. 歸併排序的空間複雜度

 上面討論了時間複雜度，接下來討論空間複雜度，這裡的空間複雜度就比較簡單了，因為整個演算法只聲明了一個額外的變數 temp_array ，大小為n。所以總的空間使用的空間，就是temp_array所佔用的空間 加上 遞歸時壓入棧的空間，也就是 n + logⁿ, 因此歸併的空間複雜度就是O(n).

4. 總結

這篇文章寫的比較短，主要是省略了歸併排序時間複雜度的推算，因為它和 快排最優情況下的時間複雜度推算 是一樣的。而歸併的空間複雜度也是比較簡單的。最後，歸併排序是一種穩定的演算法，而快排是一種不穩定的演算法（比如：1140，如果基準點選首元素，那麼最終的結果第一個1和第二個1就會互調位置，因此不穩定）。在選擇歸併和快排的時候，需要綜合它們的時間複雜度，空間複雜度 和 穩定性 再做選擇。