4.4 求排列的逆序数

墨蓝 2022-05-08 09:20 188阅读 0赞

## 7622:求排列的逆序数 ##

描述

在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

输入

第一行是一个整数n，表示该排列有n个数（n <= 100000)。  
第二行是n个不同的正整数，之间以空格隔开，表示该排列。

输出

输出该排列的逆序数。

样例输入

6
    2 6 3 4 5 1

样例输出

提示

1. 利用二分归并排序算法（分治）；  
2. 注意结果可能超过int的范围，需要用long long存储。

> 【思路】本题思路非常简单，主要就是采用分治排序，看看里面当a\[i\]<a\[j\]时进行计数。比如说当a\[i\]=4,a\[j\]=1时，此时（4,1）是一个逆序对，由于4,5，7,8是排好序的数，所以（5,1）（7,1）（8,1）自然也是逆序对，只需要在归并排序的基础上增加一句话sum+=（m+1-i）即可。

int pb = 0;
    	int i = s, j = m+1;
    	while(i <= m && j <= e)
    	{
    		if(a[i] < a[j])
    			tmp[pb++] = a[i++];
    		else
    		{
    			tmp[pb++] = a[j++];
    			sum+=(m-i+1);
    		}
    			
    	}

![70][]

归并排序：[https://blog.csdn.net/yanyanwenmeng/article/details/82989756][https_blog.csdn.net_yanyanwenmeng_article_details_82989756]

#include<iostream>
    #define MAXN 100000
    using namespace std;
    //int t = 0;
    int a[MAXN+10];
    int b[MAXN+10];
    long long sum = 0; 
    void Merge(int a[],int s,int m,int e,int tmp[])
    { 
    	int pb = 0;
    	int i = s, j = m+1;
    	while(i <= m && j <= e)
    	{
    		if(a[i] < a[j])
    			tmp[pb++] = a[i++];
    		else
    		{
    			tmp[pb++] = a[j++];
    			sum+=(m-i+1);
    		}
    			
    	}
    	while(i <= m)//p1中的元素有多余的 
    		tmp[pb++] = a[i++];
    	while(j <= e)
    		tmp[pb++] = a[j++];
    	//cout << ++t << ":" ;
    	for(int i = 0; i < e-s+1; ++i)
    	{
    		a[s+i] = tmp[i];
    		//cout << a[s+i] << " ";
    	}
    //	cout << endl;		
    } 
     
    void MergeSort(int a[],int s, int e, int b[])
    {
    	if(s < e)
    	{
    		int m = s + (e - s)/2;//m取中间值
    		//cout << "m:" << m << endl; 
    		MergeSort(a,s,m,b);//先对前一半归并排序 
    	//	cout << endl;
    		MergeSort(a,m+1,e,b);//再将后一半归并排序 
    	//	cout << endl;
    		Merge(a,s,m,e,b);//再合并两个部分 
    		//cout << endl;
    	}
    }
    //int a[8] = {8,4,5,7,1,3,6,2};
    //int b[8];//记录中间过程 
    int main()
    {
    	int n;
    	cin >> n;
    	for(int i = 0; i < n; ++i)
    	{
    		cin >> a[i];
    	}
    	MergeSort(a,0,n-1,b);//将a数组下标为0-size-1的部分排序
    	cout << sum << endl;	 
    	return 0; 
    }

![70 1][]

[70]: /images/20220508/a4984e10230a454fb119b9dc80d4f00a.png
[https_blog.csdn.net_yanyanwenmeng_article_details_82989756]: https://blog.csdn.net/yanyanwenmeng/article/details/82989756
[70 1]: /images/20220508/76c6d651654142aeb5a298c2481d3e62.png