逆序對

設 A 為一個有 n 個數字的有序集 (n>1)，其中所有數字各不相同。

如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 <A[i], A[j]> 這個有序對稱為 A 的一個逆序對，也稱作逆序數。

基本介紹

• 中文名：逆序對
• 外文名：Count Inversions
• 例如：數組（3，1，4，5，2）
• 問題描述：一個數組，求數組中多少個逆序對
• 求解方法：利用兩重循環進行枚舉或歸併排序

定義

對於一個包含N個非負整數的數組A[1..n]，如果有i < j，且A[ i ]>A[ j ]，則稱(A[ i] ,A[ j] )為數組A中的一個逆序對。

例如，數組（3，1，4，5，2）的逆序對有(3,1),(3,2),(4,2),(5,2)，共4個。

求解逆序對個數問題

問題描述

給定一個數組，求該數組中包含多少個逆序對。

求解方法

方法一：最原始的方法，利用兩重循環進行枚舉。該算法的時間複雜度為O(n^2)。

C++代碼如下：

int count_inversion(int a[], int n){    int count = 0;    for(int i = 0; i < n - 1; ++i)        for(int j = i + 1; j < n; ++j)            if(a[i] > a[j]) count += 1;    return count;}

Pascal代碼如下：

var  i,j,k,n:longint;  a:array[1..1000000] of longint;begin  readln(n);  for i:=1 to n do read(a[i]);  k:=0;  for i:=1 to n-1 do  for j:=i+1 to n do  if a[i]>a[j] then inc(k);  writeln(k);end.

方法二：利用歸併排序的思想求解逆序對的個數，這是解決該問題的一種較為高效的算法。該算法的時間複雜度為O(nlogn)。

C++代碼如下：

void merge_inversion(int *a, int l, int m, int r){    int i, j, k;    int n1 = m-l+1;    int n2 = r-m;    int *L = (int*)calloc(n1, sizeof(int));    int *R = (int*)calloc(n2, sizeof(int));    for(i=l; i<=m; i++)        L[i-l] = a[i];    for(j=m+1; j<=r; j++)        R[j-m-1]=a[j];    i = 0;    j = 0;    for(k=l; k<=r; k++)    {        if(i<n1&&j<n2)        {            if(L[i]<R[j])            {                a[k]=L[i++];                globa_count+=n2-1-j+1;            }            else            a[k]=R[j++];        }        else        break;    }    //process if one part terminately early    if(i==n1 && j<n2)        while(j<n2)            a[k++] = R[j++];    if(i<n1 && j==n2)        while(i<n1)            a[k++] = L[i++];    free(L);    free(R);}

Pascal代碼如下：

Type arr=array[1..1000000]of longint;Var i,n:longint;    k:int64;    a,b:arr;Procedure merge(var a:arr;l,x,r:longint); var i,j,p:longint;//p:position begin  i:=l;  j:=x+1;  p:=l;  while (p<=r) do begin   if(i<=x)and((j>r)or(a[i]<=a[j])) then begin     b[p]:=a[i];     inc(i);     end   else begin    b[p]:=a[j];    inc(j);    inc(k,x-i+1);    end;   inc(p);  end;  for i:=l to r do a[i]:=b[i]; end;Procedure msort(var a:arr;l,r:longint); var x:longint; begin  if (l<>r) then begin  x:=(l+r)div 2;  msort(a,l,x);  msort(a,x+1,r);  merge(a,l,x,r);  end; end;Begin readln(n); for i:=1 to n do read(a[i]); k:=0; msort(a,1,n); writeln(k);End.