求排列的逆序数

考虑1,2,…,n (n <= 100000)的排列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的一个排列，求它的逆序数。

分治O(nlogn)：
1） 将数组分成两半，分别求出左半边的逆序数和右半边的逆序数
2） 再算有多少逆序是由左半边取一个数和右半边取一个数构成(要求O(n)实现）

2) 的关键：左半边和右半边都是排好序的。比如，都是从大到小排序的。这样，左右半边只需要从头到尾各扫一遍，就可以找出由两边各取一个数构成的逆序个数

代码如下：

#include <iostream>

using namespace std;

const int maxn = 1000005;

long long a[maxn];
long long t[maxn];

void merge_sort_and_count(long long a[], int s, int e, long long t[]);

void merge(long long a[], int s, int m, int e, long long t[]);

long long count = 0;

int main() {
	int times

最后

以上就是落寞宝贝为你收集整理的求排列的逆序数的全部内容，希望文章能够帮你解决求排列的逆序数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。