p-7-9求逆序对数目

1. 逆序对的定义

设A[1.n]是一个包含n个不同数的数组，如果在i<j的情况下，有A[i]>A[j]， 则(i,j) 就称为A中的-一个逆序对。因为重
点是如何找出逆序对的数目，所以在这里假设数组的元素都不重复。

2. 求解思想

假设我们要对两个已经排好序的子序列L[1…N1],R[…N2]进行合并然后得出逆序对数目(这里注意在R的“左边”)。
如果L的某-一个元素比R的-一个元素大，比如L[2]> R[3]，由于L跟R都是升序，那么L
往后的每个元素都比R[3]大。所以比R[3]大的数量就增加N1-2个，这里的N1代表L数组的长度。
循环下去,就可以找出L跟R数组里面所有的逆序对数目了
。这里不需要担心会发生重复计数。因为L跟R各自的逆序对数目之前已经求出，合并这一步比较的是两个子数组元素，不可能重复比较。

#include <bits/stdc++.h>
using namespace std;
int  count1 = 0;
void Merge(int a[], int low, int mid , int high){
	int i = low, j = mid + 1, k = 0;
	int *temp = (int *) malloc ((high - low + 1) * sizeof(int));
	while(i <= mid && j <= high){
		if(a[i] <= a[j])
			temp[k++] = a[i++];
		else{
			count1 += mid - i + 1;
			temp[k++] = a[j++];
		}
	}
	while(i <= mid)
		temp[k++] = a[i++];
	while(j <= high)
		temp[k++] = a[j++];
	for(k = 0, i = low; i <= high ; k++,i++)
		a[i] = temp[k];	
	free(temp);
}

void MergeSort(int a[], int s, int t){
	if(s < t){
		int mid = (s + t) / 2;
		MergeSort(a, s, mid);
		MergeSort(a, mid + 1, t);
		Merge(a, s, mid, t);
		
	}
}

void disp(int arr[], int n) {
	for(int i = 0; i < n; i++)
		cout << " "<< arr[i];
	cout << endl;
}

int main(){
	int n;
	cin >> n;
	int a[n]
	for(int i = 0; i < n; i++)
		cin >> a[i];
	disp(a,n);
	MergeSort(a, 0, n - 1);
	disp(a,n);
	cout << "逆序对的个数为：" << count1;
	return 0;
}