输出

2:求排列的逆序数
查看
提交
统计
提问
总时间限制:

1000ms

内存限制:

65536kB

描述

在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
样例输出

8
直接二重循环计算的复杂度是，注意到如果前后分成两段是排好序的，那么逆序数，依次可以计算出所有逆序数，为

mid - p1+1，这就是算法的核心

实现归并排序归并的时候，需要辅助的空间，最后在将辅助空间排序好的结果复制给原数组，在函数中传入辅助数组是为了节省空间。另外为了简单，逆序数答案直接用全局变量输出了

#include
#define N 100010
using namespace std;
long long ans;
void Merge(int a[], int s, int m, int e,int temp[])
{
//将数组a的局部a[s,m]和a[m+1，e]合并到temp，保证temp有序
int pb = 0;
int p1 = s;
int p2 = m + 1;
while (p1 <= m && p2 <= e)
{
if (a[p1] < a[p2])
{
temp[pb++] = a[p1++];
}
else
{
ans += m - p1 + 1;
temp[pb++] = a[p2++];

	}
}
while (p1 <= m)
{
	temp[pb++] = a[p1++];
}
while (p2 <= e)
{
	temp[pb++] = a[p2++];
}
for (int i = 0; i < e - s + 1; i++)
{
	a[s + i] = temp[i];
}

}

void MergeSort(int a[], int s, int e, int temp[])
{
// s为a开始下标，e为结束的下标
if (s < e)
{
int m = s + (e - s) / 2;
MergeSort(a, s, m, temp);
MergeSort(a, m + 1, e, temp);
Merge(a, s, m, e, temp);
}

}

int main()
{
int size;
int a[N];
int b[N];
scanf_s("%d", &size);
for (int i = 0; i < size; i++)
{
scanf_s("%d", &a[i]);
}

MergeSort(a, 0, size - 1, b);
/*for (int i = 0; i < size; i++)
{
	cout << a[i] << " ";
}
cout << endl;*/
cout << ans << endl;
return 0;

}

归并排序的直观写法，关键在于合并两个数组的过程

#include<stdio.h>
void merge(int a[], int first, int middle, int last, int temp[])
{
int i = first, j = middle + 1, k = 0;
int l;
while (i <= middle && j <= last)
{
if (a[i] < a[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = a[j++];
}
}
if (i == middle + 1)
{
for (l = j; l <= last; l++)
{
temp[k++] = a[l];
}
}
if (j == last + 1)
{
for (l = i; l <= middle; l++)
{
temp[k++] = a[l];
}
}
for (l = 0; l < last - first + 1; l++)
{
a[first + l] = temp[l];
}

}

void mergeSort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = first + (last - first) / 2;
mergeSort(a, first, mid, temp);
mergeSort(a, mid+1, last, temp);
merge(a, first, mid, last, temp);
}
}
int main()
{
int a[10] = { 9,8,7,6,5,4,3,2,1 };
int b[10];
mergeSort(a, 0, 8, b);
for (int i = 0; i < 9; i++)
printf("%d ", a[i]);

}
 
————————————————
版权声明：本文为CSDN博主「wwxy261」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wwxy1995/article/details/82953957