ACM：歸並排序，以及利用歸並排序思想求解逆序對數！

（一）歸並排序

分析：

（1）劃分問題：把序列分成元素個數盡量相等的兩半。

（2）遞歸求解：把兩半元素分別排序。

（3）合並問題：把兩個有序表合並成一個。（每次只需要把兩個序列的最小元素加以比較，刪除其中的較小元素並加入合並後的新表）

#include 
using namespace std;

const int MAXN = 1000;
int A[MAXN], T[MAXN];

void merge_sort(int *A, int x, int y, int *T) {
	if(y - x > 1) {
		int m = x + (y - x) / 2;     //劃分
		int p = x, q = m, i = x;
		merge_sort(A, x, m, T);      //遞歸求解
		merge_sort(A, m, y, T);      //遞歸求解
		while(p < m || q < y) {
			if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];   //從左半數組復制到臨時空間
			else T[i++] = A[q++];    //從右半數組復制到臨時空間
		}
		for(i = x; i < y; ++i) A[i] = T[i];   //從輔助空間復制回A數組
	}
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> A[i];
	merge_sort(A, 0, n, T);
	for(int i = 0; i < n; ++i) cout << A[i] << endl;
	return 0;
}

首先，只要有一個序列非空，就要繼續合並while(p < m || q < y)。

其次對於：if(q >= y || (p < m && A[p] <= A[q]))。

（1）如果第二個序列為空，這個時候第一個序列肯定非空，不然就不能進入while循環，這個時候復制A[p]。

（2）否則（第二個序列非空），當且僅當第一個序列也非空，且A[p] <= A[q]時，才復制A[p]。

（二）利用歸並排序思想求解逆序對數

題目：給一列數，求它的逆序對數！

分析，由於n可能很大，所以O(n2)的枚舉方法肯定超時。所以要用分治的方法！

（1）劃分問題：把序列分成元素個數盡量相等的兩半。

（2）遞歸求解：統計i和j均在左邊或者均在右邊的逆序對個數。

（3）合並問題：統計i在左邊，j在右邊的逆序對個數。

劃分以後，對於右邊的每個j，統計左邊比它大的元素個數f(j)，則所有f(j)之和便是答案。

所以由於我們的歸並排序操作是從小到大進行的，當右邊的A[j]復制到T中時，左邊還沒有來得及復制到T的那些數就是左邊所有比A[j]大的數。

所以此時在累加器中加上左邊元素個數m-p就可以了！

#include 
using namespace std;

const int MAXN = 1000;
int A[MAXN], T[MAXN];

void inverse_pair(int *A, int x, int y, int* cnt, int *T) {
	if(y - x > 1) {
		int m = x + (y - x) / 2;     //劃分
		int p = x, q = m, i = x;
		inverse_pair(A, x, m, cnt, T);      //遞歸求解
		inverse_pair(A, m, y, cnt, T);      //遞歸求解
		while(p < m || q < y) {
			if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];   //從左半數組復制到臨時空間
			else {
				T[i++] = A[q++];    //從右半數組復制到臨時空間
				*cnt += m-p;  //更新累加器
			}
		}
		for(i = x; i < y; ++i) A[i] = T[i];   //從輔助空間復制回A數組
	}
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> A[i];
	int cnt = 0;
	inverse_pair(A, 0, n, &cnt, T);
	cout << cnt << endl;
	return 0;
}