求一个数倒序的算法

① 怎么算逆序数急~~~！！！

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

举个例子：

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

(1)求一个数倒序的算法扩展阅读：

其它算法：

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

一．
预备知识
.
这部分就是网络上一搜一大片的东西，不过还是强调一下。
.
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元排列，它的逆序数存在且唯一。那么反过...

③ 逆序数怎么算

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

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

PrivateFunctionNiXuShu(ByVallAsString)AsLong'逆序数计算

DimiAsInteger,jAsInteger,cAsLong

Dimn()AsInteger

ReDimn(Len(l))

Fori=1ToLen(l)

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

For j=1Toi-1

If n(i)<n(j)Then

c=c+1

EndIf

Nextj

Nexti

NiXuShu=c

EndFunction

逆序数归并排序

直接计数法虽然简单直观，但是其时间复杂度是O（n²）。一个更快（但稍复杂）的计算方法是在归并排序的同时计算逆序数。下面这个C++编写的例子演示了计算方法。函数 mergeSort() 返回序列的逆序数。

int is1[n],is2[n];// is1为原数组，is²为临时数组，n为个人定义的长度

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;

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