背景

? ? ?逆序數：也就是說，對于n個不同的元素，先規定各元素之間有一個標準次序（例如n個 不同的自然數，可規定從小到大為標準次序），于是在這n個元素的任一排列中，當某兩個元素的先后次序與標準次序不同時，就說有1個逆序。一個排列中所有逆序總數叫做這個排列的逆序數。

定義

在一個排列中，如果一對數的前后位置與大小順序相反，即前面的數大于后面的數，那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。

問題求解

分治法求逆序數相當于在歸并排序的過程中加上相應的逆序數的數目。

假設數組A被劃分成前半部分(A[left]->A[mid]),后半部分(A[mid+1],A[right])

假設前半部分與后半部分各自都是從小到大排好序的，若A[left]<A[mid+1]那么由A[mid+1]這個數與數組前半部分造成的逆序數目是mid-left+1，這個數在接下來的逆序數中不用再考慮，反之類同。

使用分治法解決該問題的時間復雜度為O(N*log(N)).

代碼如下：

1 #include<iostream> 2 #include<conio.h> 3 using namespace std; 4 int merge(int *A,int left,int mid,int right){ 5 int *temp=new int[right-left+1]; 6 int num=0; 7 int i=left; 8 int j=mid+1; 9 int k; 10 int index=0; 11 for(;i<=mid&&j<=right;){ 12 if(A[i]>A[j]){ 13 num+=mid-i+1; 14 temp[index]=A[j]; 15 j++; 16 } 17 else{ 18 temp[index]=A[i]; 19 i++; 20 } 22 index++; 23 } 24 //i=mid的時候，A[i]位置的數還未填充到數組temp中 25 //因此判斷條件包含等于號 26 if(i<=mid) 27 for(;i<=mid;i++){ 28 temp[index]=A[i]; 29 index++; 30 } 32 if(j<=right) 33 for(;j<right;j++){ 34 temp[index]=A[j]; 35 index++; 36 } 3738 for(k=0;k<right-left+1;k++) 39 A[left+k]=temp[k]; 40 41 delete []temp; 42 return num; 43 } 45 int inversion(int *A,int left,int right){ 46 if(left>=right) 47 return 0; 48 int mid=(left+right)/2; 49 int num1=inversion(A,left,mid); 50 int num2=inversion(A,mid+1,right); 51 return num1+num2+merge(A,left,mid,right); 54 } 55 int main() 56 { 57 int A[5]={9,8,7,6,5}; 58 cout<<inversion(A,0,4)<<endl; 59 _getch(); 60 }

?

?

轉載于:https://www.cnblogs.com/ChrisLi/p/3798858.html

總結

以上是生活随笔為你收集整理的分治法求一个N个元素数组的逆序数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。