分治演算法合並排序

A. 歸並排序

歸並排序 （Merge sort，或mergesort），是創建在歸並操作上的一種有效的排序演算法，效率為 。1945 年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。

這裡面提到了兩個概念，分別是 分治（法） 和 遞歸 ，它們是什麼呢？

分治法（Divide and Conquer）是基於多路分支遞歸求和的一種很重要的演算法範式。字面上的解釋是「分而治之」，就是把一個復雜的問題分成兩個或更多凱宏的相同或相似的子問題，再把子問題分成更小的子問題，直到最後子問題可以簡單的直接求解，原問題的解就是子問題的解的合並。這個技巧是很多高效演算法的基礎，如排序演算法中的快速排序和歸並排序，傅立葉變換中的快速傅立葉變換…

分治模式在每層遞歸時都有三個步驟：

遞歸（英語：Recursion），又譯為遞回， 在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況，如函數的定義中使用函數自身的方法。遞歸一詞還較常用於描述以自相似方法重復事物的過程。 例如，當兩面鏡子相互之間睜叢近似平行時，鏡中嵌套的圖像是以無限遞歸的形式出現的。 也可以理解為自我復制的過程。

歸並排序演算法完全遵循分治模式，直觀上，其操作步驟如下：

當待排序的序列長度為 1 時，遞歸「開始回升」，在這種情況下無須作任何工作，因為長度為 1 的每個序列都已排好序。

MERGE 的詳細工作過程如下：

我們必須證明第 12～17 行 for 循環的第一次迭代之前該循環不變式成立，且在該循環的每次迭代時保持該不變式，當循環終止時，該不變式須提供一種有用的性質來證明演算法的正確性。

前面我們分析了分治演算法的過程，我們可以把 MERGE 作為歸並排序演算法中的一個子程序來用。

上面已經對分治法做悉孫櫻了正確性證明，歸並排序的正確性不言而喻。

分治演算法運行時間的遞歸式來自基本模式的三個步驟，即分解、解決和合並。假設 T(n) 是規模為 n 的一個問題的運行時間。若問題規模足夠小，如對某個常量 c，n≤c，則直接求解需要常量時間，可以將其寫成 O(1)。假設把原問題分解成 a 個子問題，每個子問題的規模是原問題的 1/b。為了求解一個規模為 n/b 的子問題，需要 T(n/b) 的時間，所以需要 aT(n/b) 的時間來求解 a 個子問題。如果分解問題成子問題需要時間 D(n)，合並子問題的解成原問題的解需要時間 C(n)，那麼得到遞歸式：

現在我們來討論歸並排序。假定問題規模是 2 的冪（不是 2 的冪時也能正確地工作），歸並排序一個元素的時間是常量，當有 n>1 個元素時，分解運行的時間如下：

為了分析歸並排序，我們可以將 D(n) 與 C(n) 相加，即把一個 函數與另一個 函數相加，得到的和是一個 n 的線性函數，即 。把它與來自「解決」步驟的項 2T(n/2) 相加，將給出歸並排序的最壞情況的運行時間

將遞歸式重寫，得到

其中，常量 c 代表求解規模為 1 的問題所需要的時間以及在分解步驟與合並步驟處理每個數組元素所需要的時間。(相同的常量一般不可能剛好即代表求解規模為 1 的問題的時間又代表分解步驟與合並步驟處理每個數組元素的時間。通過假設 c 為這兩個時間的較大者並認為我們的遞歸式將給出運行時間的一個上界，或者通過假設 c 為這兩個時間的較小者並認為我們的遞歸式將給出運行時間的下界，我們可以暫時迴避這個問題。兩個界的階都是 ，合在一起將給出運行時間為 )。

求解遞歸式的過程如下圖所示：

可以看出，樹根 cn 通過遞歸分解，直到規模降為 1 後，每個子問題只要代價 c。分解步驟一共經歷了 次，即樹高為 層，每層的代價為 cn，因此總代價為 。

上面我們已經知道了，總代價為 ，忽略低階項和常量 c，歸並排序的時間復雜度為 O(nlogn)。

歸並排序的合並函數，在合並兩個有序數組為一個有序數組時，需要藉助額外的存儲空間，但是這個申請額外的內存空間，會在合並完成之後釋放，因此，在任意時刻，只會有一個臨時的內存空間在使用，臨時內存空間最大也不會超過 n 個數據的大小，所以空間復雜度是 O(n)。

Javascript 遞歸版

Go

迭代版

遞歸版

B. 歸並排序演算法是什麼

歸並排序（Merge Sort）是建立在歸並操作上的一種有效，穩定的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。

歸並操作的工作原理如下：

第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列。

第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置。

第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置。

重復步驟3直到某一指針超出序列尾。

將另一序列剩下的所有元素直接復制到合並序列尾。

C. 什麼是分治法的合並排序

分治法、是一種很重要的演算法。字面上的解釋是「分而治之」，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。這個技巧是很多高效演算法的基礎，如排序演算法(快速排序，歸並排序)，傅立葉變換(快速傅立葉變換)……
合並排序、是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。 將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。
都是網路復制來的，別鄙視。以解決問題為根本原則。對你有幫助就好！

D. 分治演算法幾個經典例子

分治法，字面意思是「分而治之」，就是把一個復雜的1問題分成兩個或多個相同或相似的子問題，再把子問題分成更小的子問題直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合並，這個思想是很多高效演算法的基礎。

圖二

大整數乘法

Strassen矩陣乘法

棋盤覆蓋

合並排序

快速排序

線性時間選擇

最接近點對問題

循環賽日程表

漢諾塔