逆序相加心演算法

『壹』 逆序數怎麼算

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

舉個例子：

標准列是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)逆序相加心演算法擴展閱讀：

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。

也就是說，對於n個不同的元素，先規定各元素之間有一個標准次序（例如n個 不同的自然數，可規定從小到大為標准次序），於是在這n個元素的任一排列中，當某兩個元素的實際先後次序與標准次序不同時，就說有1個逆序。

『貳』 c語言如何實現一個正序數組和一個逆序數組相加

若已知數組a[],b[]的大小為n, 那麼 用 對應 數組元素 a[i]+b[n-i-1] 即可。
例如：
int a[5]={1,2,3,4,5}, b[5]={10,9,8,7,6},sum[5];
int i,n;
n=5;
for (i=0;i<n;i++) sum[i]=a[i]+b[n-i-1]; //對應的元素相加
for (i=0;i<n;i++) printf("%d ",sum[i]); //輸出結果

『叄』 當排列數中出現相同的數時，逆序數怎麼計算，比如145243

逆序數是指一個排列中所有逆序總數，而排列，是從n個不同元素中取出m（m≤n）個元素，按照一定的順序排成一列。

145243中出現出現相同的數4， 所以145243不是排列，也就無所謂計算逆序和逆序數了。

逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。[1]如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。

(3)逆序相加心演算法擴展閱讀

計算逆序數：

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

『肆』 線性代數: 34215的逆序數是，怎麼求，需要過程

34215的逆序數是5。

方法：

1、3後面有兩個比它自己小的數，逆序數為2

2、4後面有兩個比它自己小的數，逆序數為2

3、2後面有一個比它自己小的數，逆序數為1

4、1後面沒有比它小的數，逆序數為0

5、5後面沒有比它小的數，逆序數為0

將以上所有逆序數相加便得到總的逆序數為5。

注意：這里的「後面」都是以所取數為起點往右看。

(4)逆序相加心演算法擴展閱讀：

在一個排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那麼它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。一個排列中所有逆序總數叫做這個排列的逆序數。換句話講，對於n個不同的元素，先規定各元素之間有一個標准次序（例如n個 不同的自然數，可規定從小到大為標准次序），於是在這n個元素的任一排列中，當某兩個元素的先後次序與標准次序不同時，就說有1個逆序。一個排列中所有逆序總數叫做這個排列的逆序數。

求逆序數的具體方法：

取排列中的每一個數，都以所取數為起點往右看，將所有的取數的逆序數相加便可得到排列的逆序數。

『伍』 當排列數中出現相同的數時，逆序數怎麼計算，比如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元排列，它的逆序數存在且唯一。那麼反過...

『陸』 線性代數: 34215的逆序數是，怎麼求，需要過程

解：
3排在第一位，逆序數0
4前面是3，比4小，逆序數是0
2前面比2大的是3、4，逆序數是2
1前面比1大的是2、3、4，逆序數是3
5前面沒有比5大的，逆序數是0
t=0+0+2+3+0=5
34215的逆序數是5

『柒』 什麼叫逆序

跟標准列相反序數的總和
比如說
標准列是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

這樣能明白嗎

『捌』 什麼是逆序數,計算一下1432的逆序數是幾

你好逆序數就是從左邊第一個數開始計算，後面的數有幾個比左邊第一個小的話，逆序數就是幾。然後從左邊到右邊，逐一數字計算出逆序數，然後總數相加。
比如1432
第一位是1，右邊所有數都比1大，逆序數為0。
第二位4，它的右邊兩個數都比4小，逆序數是2
類似數出逆序數，然後累加。
1432的逆序數是3

『玖』 怎麼算逆序數急~~~！！！

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

舉個例子：

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

(9)逆序相加心演算法擴展閱讀：

其它演算法：

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、樹狀數組

由於樹狀數組的特性，求和是從當前節點往前求，所以，這里要查詢插入當前數值之時，要統計有多少個小於該數值的數還沒插入，這些沒插入的數，都會在後面插入，也就形成了逆序數。

『拾』 【行列式】8、逆序數與行列式

這是一個范德蒙行列式，兩種求法，求法不同，答案一致。一是按照范德蒙行列式的結果，從第二行入手，二是展開，這里最後一列展開， 的餘子式是 即 的系數是 。兩種求法聯系起來，即求出范德蒙結果，並從中找出 的系數即可求出答案。

展開法（只寫出一項展開）：

范德蒙求法：

將含有 放前面

所以 的系數：

所以

n個不同的元素排成一列，稱為n個元素的全排列。
如：12345678，76532184，等等均為8個元素的全排列。
n個元素的全排列共有n！個。

全排列123···n稱為標准排列，此時元素之間的順序稱為標准順序。在任一排列中，若某兩個元素的順序與標准順序不同，就稱這兩個元素構成了一個逆序。
例：213中，2和1構成一個逆序。321中，1和2,1和3,2和3都構成逆序。

在一個排列中，逆序的總和稱為逆序數。如213的逆序數為1，321的逆序數為3。

逆序數怎樣求？？？
從第一個元素起，該元素前有幾個數比它大，這個元素的逆序就是幾。將所有元素的逆序相加，即得到排列的逆序數。

例：求全排列135…（2n-1）24…（2n）逆序數。
解：1，3，5，···（2n-1）不構成逆序.
2前面有n-1個數比它大，故有n-1個逆序.
4前面有n-2個數比它大，故有n-2個逆序.
依次下去，2n前面沒有數比它大，故沒有逆序.
將所有元素的逆序相加，得逆序數：
1+2+3+…+（n-1）=n（n-1）/2

逆序數為奇數的排列稱為奇排列，逆序數為偶數的排列稱為偶排列。如：
在3個元素的全排列中：
123，231，312為偶排列，逆序數分別為0，2，2.
132，213，321為奇排列，逆序數分別為1，1，3.
？：兩個數對調，奇偶排列發生轉化
？：奇偶排列各佔一半

在一個排列中，任意對調兩個元素，其餘元素不變，即得到一個新排列，這樣一種變換稱為對換。

對換有兩個性質：
1.任意一個排列經一次對換後改變奇偶性.
2.在n個元素的全排列中，奇偶排列各佔一半，為n!/2.
(當n>=2時，n!一定為偶數)

性質1的證明：
對換有兩種,一種相鄰，一種不相鄰.

若a比b大，對換後則逆序數減少一個，其餘不變，所以全排列就會奇變偶，或偶變奇。若a比b小，對換後則逆序數增加一個，其餘不變，所以全排列就會奇變偶，或偶變奇。

a與後面的一個個對換，對換到b後面，因為還要和b對換，所以需對換L+1次，a對換結束後，b再一個一個對換到前面，需要對換L次。所以總共對換2L+1次，相鄰對換一次，奇偶變一次，2L會抵消對換，1才起作用，所以變一次，即奇變偶，或偶變奇。

性質2的證明：
假設n個元素的全排列中，有p個奇排列，有q個偶排列。把p個奇排列變化一次，變為偶排列，此時變化得到的偶排列還是屬於全排列中的，所以得出p<=q，同理可證q<=p，結合兩者得p=q，所以在全排列中奇偶排列各佔一半。

這六項下標的第二個數是123的全排列，第一個數保持123不變，而正負號為逆序數的奇偶決定。

由三階行列式可得如下結論

(1) 為 的逆序數。

(2)

即對1,2,3的全排列求和。

個數排成的一個 行 列的記號

其中 為全排列 的逆序數。有時簡記為

例1：

例2：

例3.

附：