逆序对

问题

给一列数<a1,a2,…,an>,求它的逆序对，即有多少个有序对（i.j）,使得i<j且ai<aj; n 可以高达106

分析

利用归并排序中的递归 将部分排序之后对照l-mid 和mid+1-r 的逆序对个数 利用递归减少执行次数 时间复杂度变为nlogn

代码

#include<iostream>

using namespace std;

//给一列数<a1,a2,......,an>,求它的逆序对，
//即有多少个有序对（i.j）,使得i<j且ai<aj; n 可以高达106
int N;
int a[1000];
int b[1000];
int sum = 0;

void Copy(int a[], int b[], int l, int r){
	
	for(int i=l; i<=r; i++)
	a[i] = b[i];
	
}

void Sum(int l, int mid, int r){
	
	for(int i = r; i>mid; i--){
		for(int j = mid; j>=l; j--)
			if(a[i]>a[j])
				sum++;
	} 
	
}

void Merge(int a[], int l, int r, int mid){
	
	int L[mid-l+2];
	int R[r-mid+2];
	int q = 1, p = 1; 
	for(int i=l; i<=mid; i++){
		L[q++] = a[i];
	} 
	for(int i=mid+1; i<=r; i++){
		R[p++] = a[i];
	}
	
	L[q] = 100000;
	R[p] = 100000;
	
	int o = l;
	int m = 1,n = 1;
	while(m<=q || n<=p){
		if(L[m]<=R[n]){
			b[o++] = L[m];
			m++;
		}
		else {
			b[o++] = R[n];
			n++;
		}
	}
	
}

//利用归并算法中的递归算法
void MergeSort(int a[], int l, int r){
	
	if(l==r) return;
	
	int mid = (l+r)/2;
	
	//先递归l-mid
	MergeSort(a, l, mid);
	//递归mid+1-r
	MergeSort(a, mid+1, r);
	
	//计算两数组中的逆序对个数
	Sum(l, mid, r);
	//将两个数组正序
	Merge(a, l, r, mid);
	Copy(a, b, l, r);
	
}

int main(){
	
	cin>>N;
	
	for(int i=1; i<=N; i++)
		cin>>a[i];
	
	//利用归并排序的思想 将部分数组排序 找前面的数组和后一数组的关系
	MergeSort(a, 1, N);
	
	cout<<sum;
	 
//	for(int i=1; i<=N; i++)
//		cout<<a[i]<<" ";

	return 0;
}