逆序对的求解逆序对个数问题

逆序对的求解逆序对个数问题

方法一：最原始的方法，利用两重循环进行枚举。该算法的时间复杂度为O(n^2)。
C++代码如下： int count_inversion(int *a, int N){    int count = 0;    int i, j;    for(i=0; ia[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(ir)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.