首页 > 代码库 > ACM:归并排序,以及利用归并排序思想求解逆序对数!

ACM:归并排序,以及利用归并排序思想求解逆序对数!

(一)归并排序

分析:

(1)划分问题:把序列分成元素个数尽量相等的两半。

(2)递归求解:把两半元素分别排序。

(3)合并问题:把两个有序表合并成一个。(每次只需要把两个序列的最小元素加以比较,删除其中的较小元素并加入合并后的新表)

#include <iostream>
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 <iostream>
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;
}