定义

求解逆序对个数问题(问题描述 求解方法)

定义

对于一个包含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;

int i,j;

for (i = 0 ;i < N ;i ++)

for(j = i + 1; j < N ;j++)

if (a[i] > a[j])

count ++;

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,k:longint;

a:arr;

procedure merge(var a:arr; l,x,r:integer);

var　i,j,p:integer;

b:arr;

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);

k:=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:integer);

var x:integer;

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.