逆序数计算方法

‘壹’ 2n（2n-2）.....2（2n-1）(2n-3)...1的逆序数怎么求，求详细过程

2n（2n-2）.....2（2n-1）(2n-3)...1的逆序数

=(2n-1)+(2n-2-1)+(2n-4-1)+...+(2-1)+1/2((2n-1-1)+(2n-3-1)+...+(1-1))

=(2n-1)+(2n-3)+(2n-5)+...+1+1/2((2n-2)+(2n-4)+...+0)

=(2n-1+1)*n/2+1/2*(2n-2+0)*n/2)

=n^2+n(n-1)/2

=3/2n^2-1/2n

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

(1)逆序数计算方法扩展阅读：

计算一个排列的逆序数的直接方法是逐个枚举逆序，同时统计个数。例如在序列 { 2, 4, 3, 1 } 中，逆序依次为 (2,1)，(4,3)，(4,1)，(3,1)，因此该序列的逆序数为 4。

Visual Basic6.0 编写的示例使用的就是直接计数的方法，函数 NiXushu 返回一个字符串的逆序数。

Private Function NiXuShu(ByVal l As String) As Long '逆序数计算

Dim i As Integer, j As Integer, c As Long

Dim n() As Integer

ReDim n(Len(l))

For i = 1 To Len(l)

n(i) = Val(Mid(l, i, 1))

For j = 1 To i - 1

If n(i) < n(j) Then

c = c + 1

End If

Next j

Next i

NiXuShu = c

End Function

‘贰’ 逆序数 公式

n(n-1)/2是排列n(n-1)…321的公式
317428695
在3前比3的有0个
在1前比1的有1个
在7前比7的有0个
以此类推
逆序数=0+1+0+1+3+0+2+0+3=10

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

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

举个例子：

标准列是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。

(3)逆序数计算方法扩展阅读：

其它算法：

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、树状数组

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

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

逆序数是指一个排列中所有逆序总数，而排列，是从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列。

145243中出现出现相同的数4， 所以145243不是排列，也就无所谓计算逆序和逆序数了。

逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。[1]如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。

(4)逆序数计算方法扩展阅读

计算逆序数：

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

5之前没有数，记为0.

看第二个，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

‘伍’ 逆序数怎么求

解答如下：

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

‘陆’ 求排列的逆序数有简单的方法吗

更快的的求排列的逆序数计算方法是在归并排序的同时计算逆序数。下面这个 C++ 编写的例子演示了计算方法。函数 mergeSort() 返回序列的逆序数。
int is1[n],is2[n];// is1为原数组，is2为临时数组，n为个人定义的长度。
long mergeSort(int a,int b)// 下标，例如数组int is[5]，全部排序的调用为：mergeSort(0,4)
{
if(a<b)
{
int mid=(a+b)/2;
long count=0;
count+=mergeSort(a,mid);
count+=mergeSort(mid+1,b);
count+=merge(a,mid,b);
return count;
}
return 0;
}
long merge(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
long count=0;
while(i<=mid&&j<=high)
if(is1[i]<=is1[j])// 此处为稳定排序的关键，不能用小于
is2[k++]=is1[i++];
else
{
is2[k++]=is1[j++];
count+=j-k;// 每当后段的数组元素提前时，记录提前的距离
}
while(i<=mid)
is2[k++]=is1[i++];
while(j<=high)
is2[k++]=is1[j++];
for(i=low;i<=high;i++)// 写回原数组
is1[i]=is2[i];
return count;
}

‘柒’ 逆序数的逆序数的计算

计算一个排列的逆序数的直接方法是逐个枚举逆序，同时统计个数。例如在序列 { 2, 4, 3, 1 } 中，逆序依次为 (2,1), (4,3), (4,1), (3,1)，因此该序列的逆序数为 4。下面这个 Visual Basic 6.0 编写的示例使用的就是直接计数的方法，函数 NiXushu 返回一个字符串的逆序数。
Private Function NiXuShu(ByVal l As String) As Long '逆序数计算
Dim i As Integer, j As Integer, c As Long
Dim n() As Integer
ReDim n(Len(l))
For i = 1 To Len(l)
n(i) = Val(Mid(l, i, 1))
For j = 1 To i - 1
If n(i) < n(j) Then
c = c + 1
End If
Next j
Next i
NiXuShu = c
End Function 直接计数法虽然简单直观，但是其时间复杂度是 O(n^2)。一个更快（但稍复杂）的计算方法是在归并排序的同时计算逆序数。下面这个 C++ 编写的例子演示了计算方法。函数 mergeSort() 返回序列的逆序数。
int is1[n],is2[n];// is1为原数组，is2为临时数组，n为个人定义的长度
long mergeSort(int a,int b)// 下标，例如数组int is[5]，全部排序的调用为mergeSort(0,4)
{
if(a<b)
{
int mid=(a+b)/2;
long count=0;
count+=mergeSort(a,mid);
count+=mergeSort(mid+1,b);
count+=merge(a,mid,b);
return count;
}
return 0;
}
long merge(int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
long count=0;
while(i<=mid&&j<=high)
if(is1[i]<=is1[j])// 此处为稳定排序的关键，不能用小于
is2[k++]=is1[i++];
else
{
is2[k++]=is1[j++];
count+=j-k;// 每当后段的数组元素提前时，记录提前的距离
}
while(i<=mid)
is2[k++]=is1[i++];
while(j<=high)
is2[k++]=is1[j++];
for(i=low;i<=high;i++)// 写回原数组
is1[i]=is2[i];
return count;
}

‘捌’ 怎样求逆序数

这个的是0
1后面<1的数0个＋2后面<2的数0个＋3后面<3的数0个＝0
可以推广为（a,b,c,……，z)
a后面小于a的数A个……一直加到z后面小于z的数Z个
即为它的逆序数！

‘玖’ 逆序数的计算

解答如下：
当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；
………
依次类推得排列1，3，…（2n-1),2,4,…(2n)的逆序数为
T=0+1+2+3+…+（n-1）=n（n-1）/2
补充：
这个题目是由一个奇数列与一个偶数列组成的
2是分界点，把2之前的看成一部分，2之后（包括2）的看成一部分
然后再看2n-1与2n就会知道其规律性了

‘拾’ 关于排列逆序数的计算

顺次一个一个检测各个数的【逆序数】（排列后面比它小的数的个数。（其实这不是唯一的方法，但如果连这个方法也不会也不必贪多！）），然后把各个逆序数加起来就得到整个排列的逆序数。
排列中：N[(2n)...]=2n-1
【因为后面
2n-1个数都比2n小】；
N[。。(2n-2)。。。]
=2n-3
【2n-2后面有2n-2个数，除2n-1比它大，都小】；
N'(2n-4)=2n-5
【后面有2n-3个数，2n-1、2n-3比它大】；
。。。
N'(2)=1
【只有
1
比它小】；
N'[(2n-1)]=n-1
【后面n-1个都比它小】；
N'[(2n-3)]=n-2
。。。
。。。
N‘(3)=1
【1
比它小】；
N'(1)=0
【后面没有比它小的】；
所以，排列的逆序数=N(排列）
=(2n-1)+(2n-3)+...+3+1+(n-1)+(n-2)+...+2+1+0
=[(1+2n-1)n/2]+(0+n-1)n/2
=(2n^2)/2+(n^2-n)/2
=(3n^2-n)/2
【逆序数的计算因方法的不同，数值并不唯一，但奇偶性是一定的。】