逆序数怎么求

Question

如题所述

Answer 1

解答如下： 

当n=1时，排列为1 2，逆序数t=0。

当n=2时，排列为内1 3 2 4，逆序容数t=1。 

当n=3时，排列为1 3 5 2 4 6，逆序数t=1+2=3。

当n=4时，排列为1 3 5 7 2 4 6 8，逆序数t=1+2+3=6。 

当n=5时，排列为1 3 5 7 9 2 4 6 8 10，逆序数t=1+2+3+4=10。

相关内容解释

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。

也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序(例如n个 不同的自然数，可规定从小到大为标准次序)，于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

Answer 2

我收集到的有两种方法：归并排序和树状数组。
1、归并排序：
假设a[l...r]这个数组，先二分mid=(l+r)/2；那么我们假设已经求出了a[l...mid],a[mid+1...r]这两段元素的逆序数且排好序，于是可以将这两段归并了，归并的同时计算逆序数，如果前段的数小于后段的数，属于正常排序，反之，就会有逆序数产生。假设l<=i<=mid,mid+1<=j<=r,如果有a[i]>a[j]，这样的发生说明在a的前段中i...mid的元素都比a[j]大，于是逆序数+=mid-i；如果a[i]<a[j]，这样的发生说明属于正常排序。然后将其中某段中剩余的数（全部的大数）接上，于是就求好了整个排列的排序及其逆序数。复杂度为nlogn。
2、树状数组：
我们先假设一个1...n自然数排列，n不是很大，于是这样就可以申请一个n个空间的a数组，首先全部置0，每次将排列中的数i取出（从左到右取出），改变a数组的元素的值为1（1），然后求出a[1...i-1],的和（1），这个和就是小于i的值的和sum，就是i这个数的逆序数。这里的（1）、（2）就会用到树状数组的logn时间复杂度的算法。
但是这里说自然数的范围很大比如（0-999，999，999）时候，而个数不多时。这样是情况才是作者想考察我们算法的东西，那么这里就要说说离散化的用法了。
离散化：其实我开始理解就是想的很多大数据用数组来存储，那么下标就代表了数据本身了，举个简单的列子。
1、1000、100000、100000、999。
这样一串数，如果用数组来存储，只需要开辟5个int空间就够了。这样就把离散的大数据很轻巧的装到小盒子里面了。这样说，其实你可能还在懵懂中，因为这样的方法好像随处可见，我开始也是这样想的，没什么特别的，但是当我看到了一个别人博客里做的离散化题目后才深切的体会。那么下面让我们来看看在逆序数中的用法吧！
如果将逆序数的本质找到就可以很好理解了，求逆序数其实就求每个数的逆序数之和，如果要求当前逆序数，则是找当前数的后续数中比他小的数的个数，然后在抽象一下就可以知道，其实对于逆序数而言，与元素的本身没关系，而是与元素与元素之间的大小有关系，这点理解到的很重要的。
既然是元素与元素之间大小相关的话，我们就可以这样看的问题了，对于上面的一串数可以用另外一串具有最小数据本身的数来替代，假设用3、40、50、60、20，比较一下，可以看出他们元素与元素之间的大小关系是一样的。于是我们就可以进一步推测能够找到最小串的自然数来替代了，就是1、3、4、5、2。看看吧！这串数够小了吧，而且关系和上面的大数据也相同，即是说逆序数相同。
如果找到了这样的一串数来替代大数据的话，我们就可以开小空间数组来存储这些数了。然后就可以用树状数组来求出逆序数，复杂度为nlogn。
这里就要想怎样求得这样的串了，其实稍微一想便知道，其实这串数就是大数据的排名情况。比如1000排名第3，于是1000就是3。求排名其实就是求一个排序，排序后的数组下标就是该数据的排名。于是我们会问，你怎么知道该数据和下标的对应关系呢？
假设我们为每个大数据建立起1对1的关系的话就好说了。
struct Ln
{
int a;//表示大数据
int b;//表示下标ln[i],这里的i==b
}
Ln ln[N];
建立好对应关系后，对ln排序，排好序后每个小标都有排名了，即是大数据的排名，然后将他放入a数组中，建立树状数组。
a[ln[i].b]=i;//排名存储入数组。
纵观效率问题，排序采用快排nlogn，o(n)初始化数组,nlogn，求逆序数。
效率为nlogn，和归并效率一样，只是编写起来麻烦一些，但是这里的思想远比归并来得的经典。学习才是王道！本回答被提问者和网友采纳

Answer 3

1.n(n-1)/2;,,,
2.i=8,k=3
第二小题的过程:1274i56k9成一个排列，所以(i，k)的值只能取(3，8)或(8，3)两种情况。
当(i，k)=(3，8)时，排列逆序数为1+2+1+1=5，奇排列;
当(i，k)=(8，3)时，排列逆序数为1+2+2+5=10，偶排列。

Answer 4