基于分治的歸并排序

某天得知寒假還有程式設計作業，便很無奈地寫着第一套題，發現分治算法，這種基礎算法，初一初二學的，現在完全不記得了23333

于是嘛，就又重新學了一下分治以及歸并排序。

一、啥是分治

分治，字面上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

（以上來自百度百科quq）

二、适用條件

采用分治法解決的問題一般具有的特征如下：

1. 問題的規模縮小到一定的規模就可以較容易地解決；
2. 問題可以分解為若幹個規模較小的模式相同的子問題，即該問題具有最優子結構性質；
3. 合并問題分解出的子問題的解可以得到問題的解；
4. 問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。

（還是來自百度百科，因為覺得說的很有道理就直接複制了）

三、從歸并排序入手

假設我們要排序這樣一個序列：

14，13，52，26，12，2，44，42

首先是要利用分治将這列數的排序變成小數字的排序（從上往下）：

PS：主要是二分法，這個最常用。

然後是把每個小問題排序，合并成最終答案（從下往上）：

（是不是很像一顆樹？！）

當把子問題合并時，我們隻需要用一個tmp數組存順序，最後複制回原數組即可（以最後一步為例）：

我們通過倆指針i和j比較從front到mid和mid+1到end的大小，依次放進tmp中，再複制回原數組即可（如下）。

具體見程式咯！

時間複雜度：O(nlogn)

C++ Code：

#include <bits/stdc++.h>
using namespace std;
int a[100];

void MergeSort(int* a,int f,int mid,int e){
	int* tmp = new int[e-f+2];//利用tmp詢問一個新的記憶體空間用來定義tmp數組
	int i = f,j = mid+1,k = 1;//定義指針和tmp數組初始位置
	/*比較并存入tmp過程*/
	while (i <= mid && j <= e){
		if (a[i] < a[j]) tmp[k++] = a[i++];
		else tmp[k++] = a[j++];
	}
	
	while (i <= mid) tmp[k++] = a[i++];
	while (j <= e) tmp[k++] = a[j++];
	/*複制過程*/
	k = 1;
	for (int i = f;i <= e;i++) a[i] = tmp[k++];
	delete [] tmp;//養成好習慣，有new必有delete！
}

void Merge(int* a,int f,int e){
	int mid = (f+e)/2;
	if (f < e){
		Merge(a,f,mid);
		Merge(a,mid+1,e);
		MergeSort(a,f,mid,e);
	}
}

int main(){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++)
		cin >> a[i];
	Merge(a,1,n);
	for (int i = 1;i <= n;i++) cout << a[i] << " ";
	cout << endl;
}

           

四、寫在後面

分治貌似就是和二分差不多，寫了分治求最近點對和分治求逆序數，大概懂了些皮毛了。。。

也祝大家新年快樂！！！！！！！！