逆序对算法

‘壹’ 逆序数怎么求

解答如下：

当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个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

‘贰’ 怎么算逆序数急~~~！！！

可使用直接计数法，计算一个排列的逆序数的直接方法是逐个枚举逆序，同时统计个数。

举个例子：

标准列是1 2 3 4 5，那么 5 4 3 2 1 的逆序数算法：

看第二个，4之前有一个5，在标准列中5在4的后面，所以记1个。

类似的，第三个 3 之前有 4 5 都是在标准列中3的后面，所以记2个。

同样的，2 之前有3个，1之前有4个，将这些数加起来就是逆序数=1+2+3+4=10。

(2)逆序对算法扩展阅读：

其它算法：

1、归并排序

归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；

当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数。

2、树状数组

由于树状数组的特性，求和是从当前节点往前求，所以，这里要查询插入当前数值之时，要统计有多少个小于该数值的数还没插入，这些没插入的数，都会在后面插入，也就形成了逆序数。

‘叁’ 一道编程题：求逆序对的个数

#include<stdio.h>
#define N 105
void main()
{
int n,i,j,k=0,p,m=0;
int a[20];
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
getchar();
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
k++;
}
for(i=0;i<n;i++)/*去掉相同的元素，再进行排序*/
for(j=i+1;j<n;j++)
{
if(a[i]=a[j])
{
for(p=j+1;p<n;p++)
a[p-1]=a[p];
n--;
}
}
for(i=0;i<p;i++)
for(j=i+1;j<p;j++)
{
if(a[i]>a[j])
m++;
}

printf("%d\n%d",k,m);
}//呵呵，我只会用c写，不过结果是对的。

‘肆’ 当排列数中出现相同的数时，逆序数怎么计算，比如145243

一．
预备知识
.
这部分就是网络上一搜一大片的东西，不过还是强调一下。
.
1．
全排列
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m＝n时所有的排列情况叫n的全排列。[1]对于n的全排列，共有n!种情况。
2.
逆序、逆序数和奇、偶排列
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。[2]
例如，对于n=3的全排列：
全排列
123
231
312
132
213
321
逆序数
0
2
2
1
1
3
奇偶性
偶
奇
.
二．
相关问题
.
1.
给定一个排列，求它的逆序数。[3]
问题：给定一个排列，求它的逆序数是多少。
分析：设
p1,p2,…,pn
为n的一个全排列，则其逆序数为t=t1+t2+…+tn=
其中
ti为排在pi
前，且比pi
大的数的个数。
这部分代码比较简单，此处略去。
.
2.
根据逆序数推排列数。[4]
问题：给定一个n元排列，它的逆序数存在且唯一。那么反过...

‘伍’ n阶行列式逆序数怎么算，有没有具体公式一步将逆序数

没有具体公式，算法如下：

在行列式：

显然，1,2,...,n也是一个n级排列，这个排列具有自然顺序，就是按递增的顺序排起来的；其它的排列都或多或少地破坏自然顺序。

逆序

定义2 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。

注：

1.对于n个不同的元素，先规定个元素之间有一个“标准次序”（例如n个不同的自然数，可规定由小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就有1个“逆序”。

2.一个排列中所有逆序的总数叫做这个排列的逆序数。

3.逆序数为奇数的排列叫做奇排列，逆序数为偶数的排列叫做偶排列。

‘陆’ 给定有序表A[1:n]，修改合并排序算法，求出该有序表的逆序对数

逆序对是这么定义的，在数组array中，如果存在下标i，j ，且 i<j ,但是array[i]>array[j]。这里假定array是升序的，如果是降序则相反就行。
比如说 1，5，4，3 则有逆序对 （5，3）（5，4）（4，3）

显然最笨的求逆序对的方法是，两层循环查找一遍，复杂度为O（n^2）;
目前最好的求逆序对的方法就是用分治法，也就是和归并排序类似的方法。

我大概说一下这种方法的思想，有什么不明白的直接用网络hi我。

首先将数组array从中间一分为二，假设前半部分叫left，后半部分叫right
那么，可以先递归地对left和right做归并排序，同事顺便求出它们的逆序对数;(你学归并排序了，这个应该能懂吧？)
然后，也就是最重要的一步，这时候left和right已经是有序的了，设置下标，l和r分别指向left和right的头，如果当前的l指向的元素大于r指向的元素，则r++（这时候就构成逆序对了，因为left中的元素在原数组中的下标一定小于right中的元素），一直到left[l]<=right[r]为止，这时候l++，最终到left或right扫描完终止。这其实也是归并排序的归并过程。

‘柒’ 什么叫逆序

跟标准列相反序数的总和
比如说
标准列是1 2 3 4 5
那么 5 4 3 2 1 的逆序数算法：
看第二个，4之前有一个5，在标准列中5在4的后面，所以记1个
类似的，第三个 3 之前有 4 5 都是在标准列中3的后面，所以记2个
同样的，2 之前有3个，1之前有4个
将这些数加起来就是逆序数=1+2+3+4=10

再举一个 2 4 3 1 5
4 之前有0个
3 之前有1个
1 之前有3个
5 之前有0个
所以逆序数就是1+3=4

这样能明白吗

‘捌’ 一道ACM题，求逆序对问题

一． 预备知识

.

这部分就是网络上一搜一大片的东西，不过还是强调一下。

.

1． 全排列

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m＝n时所有的排列情况叫n的全排列。[1]对于n的全排列，共有n!种情况。

2. 逆序、逆序数和奇、偶排列

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。[2]

例如，对于n=3的全排列：

全排列

123

231

312

132

213

321

逆序数

0

2

2

1

1

3

奇偶性

偶

奇

.

二． 相关问题

.

1. 给定一个排列，求它的逆序数。[3]

问题：给定一个排列，求它的逆序数是多少。
分析：设 p1,p2,…,pn 为n的一个全排列，则其逆序数为t=t1+t2+…+tn=

其中 ti为排在pi 前，且比pi 大的数的个数。

这部分代码比较简单，此处略去。

.

2. 根据逆序数推排列数。[4]

问题：给定一个n元排列，它的逆序数存在且唯一。那么反过来，已知一个n元排列的逆序数为m，
这样的n元排列有多少种？
分析：我们用f(n,m)表示逆序数为m的n元排列的个数,则求满足条件的排列个数问题就转化为求f(n,m)的值的问题。

为了得到最终结果，我们先研究f(n,m)的性质。可以得到以下几个命题：

[命题1] 对任意n>=2且0<=m<=C(n,2)时f(n,m)>=1；当m>C(n,2)时,f(n,m)=0

C(a,b)表示从a个元素中选出b个元素的选择种数

证明：先证命题1的前半部分。

(1)n=2时，m只可能是0或1.有f(2,0)=1,f(2,1)=1

(2)假设n=k时命题成立,即有f(k,m)>=1(0<=m<=C(k,2))

当n=k+1时，排列1,2,3,…,k+1满足逆序数为0,所以有f(k+1,0)>=1

若m>=1，考虑某一逆序数为m-1的k元排列a1,a2,…,ak(由归纳假设知这个排列存在).现将k+1插入到a(k-1)和ak之间得到一个k+1元排列a1,a2,…,a(k-1),k+1,ak，这个排列的逆序数为m,所以f(k+1,m)>=1

综上所述，对所有的0<=m<=C(n,2)有f(n,m)>=1

再证命题的后半部分(比较显然)。

因为对于一n元排列，若要使其逆序数达到最大，那么排列中任两个数都构成逆序，其逆序数为C(n,2)，所以不可能存在一n元排列使其逆序数大于C(n,2)

[命题2] f(n,m)=f(n,C(n,2)-m)

证明：对于一个逆序数为m的n元排列a1,a2,…,an，n元排列an,a(n-1),…,a2,a1的逆序数为C(n,2)-m.同理，对于一个逆序数为C(n,2)-m的n元排列a1,a2,…,an，n元排列an,a(n-1),…,a2,a1的逆序数为m.

于是，逆序数为m的n元排列的集合 和 逆序数为C(n,2)-m的n元排列的集合 是一一对应关系，所以f(n,m)=f(n,C(n,2)-m)

[命题3] f(n+1,m)=f(n,m)+f(n,m-1)+…+f(n,m-n)

先考虑由1,2,…,n组成的一个排列a1,a2,…,an，由于任一个由1,2,…,n,n+1构成的排列，可以看成将n+1加入的a1左边，或an的右边，或ai与a(i+1)之间(1<=i<=n-1)而形成的。又由于在n+1加入任一个位置之后，其前面没有比n+1大的数，其后面的数都比n+1小，而且加入n+1之后，使得对后面的每一个数而言，其前面比自身大的数的个数增加1，对n+1前面的数而言，其前面比自身大的个数不变。于是当选取n+1加入a1的左边时，排列a1,a2,…,an的逆序数变为m+n，当n+1加入ai与a(i+1)之间(1<=i<=n-1)时，排列a1,a2,…,an的逆序数变为m+n-i，当加入an的右边时，排列a1,a2,…,an的逆序数仍为m。

于是，对于任一逆序数为m的n+1元排列，考虑n+1所处的位置。若n+1在第k位，则其余n个元素构成逆序数为m-n+k-1的n元排列，且对任一逆序数为m-n+k-1的n元排列而言，当n+1放在该排列的某位，使得在新排列中n+1处于第k位，那么新排列成为一逆序数为m的n+1元排列。

于是，逆序数为m的n+1元排列的集合 和 逆序数为m的n元排列的集合 是一一对应关系。这样，对于一个n+1元排列，f(n,m)表示n+1排在最后的排列个数，f(n,m-1)表示n+1排在倒数第二位的排列的个数……，f(n,m-n)表示n+1排在首位的排列个数，且f(n+1,m)为这些排列之和。

所以f(n+1,m)=f(n,m)+f(n,m-1)+…+f(n,m-n)(注:记b<0时，f(a,b)=0)

[命题4] f(n,0)=f(n,C(n,2))=1

[命题5] f(n,1)=f(n,C(n,2)-1)=n-1(n>1)

证明：由命题3和命题4有

f(n,1)=f(n-1,1)+f(n-1,0)=f(n-1,1)+1

反复应用上式，根据f(2,1)=1，得到命题5成立

[命题6] f(n,2)=f(n,C(n,2)-2)=C(n,2)-1(n>2)

证明：由命题3，4，5有

f(n,2)=f(n-1,2)+f(n-1,1)+f(n-1,0)=f(n-1,2)+n-1

反复应用上式，根据f(2,2)=0，得到命题6成立

同理，可证明

f(n,3)=C(n,3)-C(n,2)-C(n,1) (n>3)

f(n,4)=C(n,4)+2C(n,3)-C(n,1) (n>4)

f(n,5)=C(n,5)+3C(n,4)+2C(n,3)-C(n,2)+1 (n>5)

…

我们可以无限递推下去，计算f(n,k)的时候要用到前面所推导出的f(n,1)~f(n,k-1)。但是却很难得到一个通项公式。这个问题就类似于用∑(k^t-(k-1)^t) 来求∑(k^(t-1))，每作下一项都要用到前面所有的结果。

由于在命题3中我们得出了一个关于f(n,m)的递推公式，而且又知道了一些初始值。因此可以设计一个程序，输入n,m，输出f(n,m)。[5]

.

参考代码：

+ View Code
.
3. 根据每个数的逆序数，然后求出原排列。[6]

复制代码
问题：对于一个集合S={1,2,3,...N}的任一排列a1、a2、a3、... aN，我们定义ai的逆序数为
∑(aj>ai | j<i)，即排在ai前的所有比ai大的数的个数。我们把每个数的逆序数按下标排出就构
成排列a1、a2、a3、... aN的一个逆序排列。比如排列 3 1 2 的逆序排列为 1 1 0(从左往右
依次是1的逆序数、2的逆序数、3的逆序数)。现在我们给出一个排列的逆序排列，请求出原排列。[7]
复制代码
分析：<developing…一种题解请参阅引用7>

.

4. 给定逆序数，求满足此逆序数的最小排列。[8]

问题：对于n的全排列，给定一个正整数m，找到满足逆序数是m的最小的排列。例如，n=5，m=4，此
时满足逆序数为4最小的排列是1 3 5 4 2。
分析：解决此问题，要先了解以下几个命题和定理。（注意，在证明中排列的大于、小于指两排列在全排列中位置的前后关系，小于即在前，大于反之）

[定理1]对于n的全排列，在它完全倒序的时候（也就是n,n-1,…,2,1的时候）逆序数最多。

证明：此处省略，可用反证法简单证明。

[命题1]对于一个形如1,2,3,…,i-1,i,n,…i+1的排列q（如n=5时的1,2,5,4,3），即在数n前保证首项为1且严格以公差为1递增而数n之后排列任意的数列，

(1)当数n之后是递减的时候q的逆序数最多，为t=C(n-i,2)。

(2)排列q是出现逆序数为t的最小排列。

证明：首先证明(1)。

这个证明很容易。因为数列的前i+1项已经确定，所以整个数列的逆序数只和i+2项到n项有关。显然，由定理1，当第i+2项到第n项完全倒序的时候逆序数最大。比如说排列1,2,5,4,3就比1,2,5,3,4构成的逆序对多。

现在证明(2)。

假设存在一个排列p的逆序数为m且p小于q。我们知道，q的前i位已经是数n在当前位置的最小排列。也就是说，在q中无论是n还是n之后的任意一个数，将它与q中的1到i位的任意一个数更换位置后得到的排列一定大于q。比如，对于排列q：1,2,5,4,3，前两个数1、2的位置是不能变的，否则会大于q，比如1,3,5,4,2。

所以我们只能从q的第i+1位到n位入手。由(1)可知，当n在第i+1位时，无论后面的数怎么排列，逆序数都无法超过m。所以p的数n一定在第i+2到第n位的任一位上。

好的，我们假设数n在第i+2位上。在这种情况下不难发现，我们把原来n后面最大的数填补到第i+1位，这时的逆序数最多。比如对于1,2,5,4,3，我们把5移动到第4位，然后将4填补到第3位，排列就变成了1,2,4,5,3，显然这要比1,2,3,5,4优。

我们分析一下这时p的逆序数。因为数n到了第i+2位，则由它构成的逆序数为n-i-2。同样，由第i+1位（也就是例子中的4，即n-1）构成的逆序数也是n-i-2。显然，由于保持了递减的特征，剩下的第i+3到第n位的逆序数为C(n-i-2,2)。（这里姑且认为C(1,2)=1）这时总的逆序数为

t1 =C(n-i-2,2)+2*(n-i-2)

=(n-i-2)(n-i-3)/2+2*(n-i-2)

=(n-i-2)(n-i+1)/2.

而q的逆序数

t2=C(n-i,2)

=(n-i)(n-i-1)/2.

用t2-t1，得到定值1。也就是说，无论n取何值，t2总是大于t1。

如果再将数n向右移动一位，这时我们只有保持前1到i+1位（即例子中的1,2,3,4）不变才能够保证之后的变换能够使逆序数最大（这个很显然，不特别证明）。然而，当前面的i+1位确定了以后，怎么变换后面的数字才能够使总逆序数最大呢？还是要原来n后面最大的数填补到第i+1位。我们已经证明，这样做是不如不换优的。所以，不存在一个小于q的排列p使p的逆序数为m。证毕。

[命题2]在命题1所设定的排列q的基础上，我们将数n后面的第k小数与数n的前一个数（即i）交换，然后使数n后面保持逆序。这样得到的新排列所含的逆序数为t=C(n-i,2)+k，且这个排列是逆序数为t的最小排列。

证明：首先，在此强调一下排列q的结构，如图一：

由于操作以后数n之后仍然保持逆序，所以从第i+1到第n位的逆序数仍为C(n-i,2)。对于x来说，交换之前后面有k-1个比它小的数，交换之后又加上了一个，所以x所拥有的逆序数（即以x为左的逆序数）为k-1+1=k,此时总的逆序数为C(n-i,2)+k。

对于新排列逆序数为t=C(n-i,2)+k的最小排列的证明与命题1的证明相似，在此处不加以详细证明。

到此我们可以得出，命题2也是真命题。

有了这两个命题作基础，我们很容易就能够得到这道题的算法。首先利用命题1，二分查找找到数n的位置，我们可以得到数n在这个位置的时候形如q的排列的逆序数t。然后计算t与m的差值，得出k，然后根据命题2进行变换，最后得出要求的排列。

.

参考代码：

+ View Code

‘玖’ c语言 请问逆序数的优化编程算法怎么做到

int getRevange(int n);

int getRevange(int n)
{
int t = 0;

for(; n; n /= 10)

t = t*10 + n%10;

return t;

}

解释一个这段程序：
假设n为12345
n%10 => 5 t = t*10 * n%10; t=> 0*10+5 => 5 n /= 10; n => 1234
n%10 => 4 t = t*10 * n%10; t=> 5*10+4 => 54 n /= 10; n => 123
n%10 => 3 t = t*10 * n%10; t=> 54*10+3 => 543 n /= 10; n => 12
n%10 => 2 t = t*10 * n%10; t=> 543*10+2 => 5432 n /= 10; n => 1
n%10 => 1 t = t*10 * n%10; t=> 5432*10+1 => 54321 n /= 10; n => 0
循环结束，t的值正好是n的逆序数。

‘拾’ 设有数组A[n],n>1,试设计一个算法,求数组A[n]的逆序

方法一：最原始的方法，利用两重循环进行枚举。该算法的时间复杂度为O(n^2)。 C++代码如下： int count_inversion(int *a,int N) { int count = 0; int i,j; for (i = 0 ;i < N ;i ++) for(j = i + 1; j < N ;j++) if (a[i] > a[j]) count ++; return count; } Pascal代码如下： vari,j,k,n:longint; a:array[1..1000000]of longint; begin readln(n); for i:=1 to n do read(a[i]); k:=0; for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then inc(k); writeln(k); end. 方法二：利用归并排序的思想求解逆序对的个数，这是目前解决该问题的一种较为高效的算法。该算法的时间复杂度为O(nlogn)。 C++代码如下： void merge_inversion(int *a,int l,int m,int r) { int i,j,k; int n1 = m - l + 1; int n2 = r - m; int *L = (int *)calloc(n1,sizeof(int)); int *R = (int *)calloc(n2,sizeof(int)); for(i = l; i <=m ;i ++) L[i-l]=a; for(j = m +1 ;j <= r ;j ++) R[j -m-1] = a[j]; i = 0 ; j = 0 ; for(k = l ;k <= r ;k ++) { if ( i < n1 && j < n2 ) { if( L < R[j]) { a[k]=L[i++]; globa_count += n2-1-j+1; } else a[k]=R[j++]; } else break; } // process if one part terminately early if (i == n1 && j < n2) while(j < n2) a[k++]=R[j++]; if (i < n1 && j == n2) while(i < n1) a[k++]=L[i++]; free(L); free(R); } Pascal代码如下： type arr=array[1..1000000]of longint; vari,n,k:longint; a:arr; procere merge(var a:arr; l,x,r:integer); vari,j,p:integer; b:arr; begin i:=l; j:=x+1; p:=l; while p<=r do begin if (i<=x)and((j>r)or(a[i]<=a[j])) then begin b[p]:=a[i]; inc(i); end else begin b[p]:=a[j]; inc(j); k:=k+x-i+1; end; inc(p); end; for i:=l to r do a[i]:=b[i]; end; procere msort(var a:arr; l,r:integer); var x:integer; begin if l<>r then begin x:=(l+r) div 2; msort(a,l,x); msort(a,x+1,r); merge(a,l,x,r); end; end; begin readln(n); for i:=1 to n do read(a[i]); k:=0; msort(a,1,n); writeln(k); end.