求一個數倒序的演算法

① 怎麼算逆序數急~~~！！！

可使用直接計數法，計算一個排列的逆序數的直接方法是逐個枚舉逆序，同時統計個數。

舉個例子：

標准列是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