在一個(gè)排列中，如果一對(duì)數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個(gè)逆序。

一個(gè)排列中逆序的總數(shù)就稱為這個(gè)排列的逆序數(shù)。逆序數(shù)為偶數(shù)的排列稱為偶排列；逆序數(shù)為奇數(shù)的排列稱為奇排列。

1.排列有奇排列和偶排列，奇排列不能轉(zhuǎn)化成偶排列，偶排列不能轉(zhuǎn)化成奇排列

2.有一個(gè)隨機(jī)排列，用f(x)(x!=0)表示數(shù)字x前面比它小的數(shù)的個(gè)數(shù)，
全部數(shù)字的f(x)之和為y，若y為奇數(shù)，則稱為奇排列，否則是偶排列
例如：

排列871526340，y=0+0+0+1+1+3+2+3=10,偶排列
排列871625340，y=0+0+0+1+1+2+2+3=9,奇排列
3.逆序數(shù)也可以理解為將一個(gè)隨機(jī)排列通過交換成為升序排列的最小交換次數(shù)

歸并排序求排列的逆序數(shù)：時(shí)間復(fù)雜度 N*log（N）

函數(shù)接口：a[0...n-1] ，cnt=0; call: MergeSort(0, n)；

逆序數(shù)為cnt；

#include<cstdio> const int maxn =1e4+10; int a[maxn]; int c[maxn]; int cnt;void MergeSort(int l, int r) {int mid, i, j, tmp;if (r > l + 1){mid = (l + r) / 2;MergeSort(l, mid);MergeSort(mid, r);tmp = l;for (i = l, j = mid; i < mid && j < r;){if (a[i] > a[j]){c[tmp++] = a[j++];cnt += mid - i;}else{c[tmp++] = a[i++];}}if (j < r){for (; j < r; ++j){c[tmp++] = a[j];}}else{for (; i < mid; ++i){c[tmp++]=a[i];}}for (i = l; i < r; ++i){a[i] = c[i];}}return ; }int main() {int N;while(scanf("%d",&N)!=EOF){for(int i=0;i<N;i++)scanf("%d",&a[i]);cnt=0;MergeSort(0,N);printf("%d\n",cnt);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【归并排序】求逆序数算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。