[알고리즘 설계] 역순 수 를 구하 다

정의
        한 배열 에서 한 쌍 의 앞 뒤 위치 가 크기 순서 와 반대 된다 면 앞의 수가 뒤의 수 보다 크 면 역순 이 라 고 부른다.하나의 배열 에서 역순 의 총 수 를 이 배열 의 역순 수 라 고 한다.역순 수 는 짝수 의 배열 을 짝수 배열 이 라 고 한다.역순 수 를 기수 로 하 는 배열 을 기 배열 이 라 고 한다.예 를 들 어 2431 에서 21, 43, 41, 31 은 역순 이 고 역순 수 는 4 로 짝 으로 배열 된다.
즉, n 개의 서로 다른 요소 에 대해 먼저 각 요소 간 에 하나의 표준 순서 (예 를 들 어 n 개의 서로 다른 자연수, 작은 것 부터 큰 것 까지 표준 순서 로 규정 할 수 있 음) 가 있 도록 규정 한다. 그래서 이 n 개의 요소 의 임 의 배열 에서 특정한 두 요소 의 선후 순서 와 표준 순서 가 같 지 않 으 면 1 개의 역순 이 있다 고 말한다.하나의 배열 중의 모든 역순 총 수 를 이 배열 의 역순 수 라 고 한다.
2. 해법 --- 폭력 구 해
         시간 복잡 도 O(n^2)

#include <stdio.h>
#include <stdlib.h>
int main() 
{
    int n;
    int i,j;
    int* a;
    int cnt=0;
    scanf("%d",&n);
    a = (int*) calloc(n, sizeof(int));
    for(i=0; i<n; ++i) {
        scanf("%d",&a[i]);
    }
    for(i=0; i<n; ++i)
        for(j=i; j<n; ++j) {
            if(a[i] > a[j]) ++cnt;
    }
    printf("%d
",cnt);

    return 0;
}

셋째, 해법 --- 분 치 법

//     o(nlogn)    
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//  b           
long long Calc(int* a, int* b, int first, int last)//long  long    
{
    if(first >= last)  //              
        return 0; 
	       
     int i,j,k,mid;
     k=i=first;
     long long res=0;//      
     
     mid=(first+last)/2;
     j=mid+1;
     res=Calc(a,b,i,mid)+Calc(a,b,j,last);  //           
     
     
     while((i<=mid) && (j<=last))//               
     {
        if(a[i]<=a[j]) //           （       ，        <          ） 
        {
        	b[k++]=a[i++];//        
			res += j-mid-1; //  j     ，        。res =0 
			printf("res=%d
",res);

		} 	   
        else
		   b[k++]=a[j++];   //        a[i]=a[j]    
     }
     
     while(i<=mid)//    ，          (       )
     {
     	 b[k++]=a[i++];
         res+=j-mid-1;	//(                    ) 
     }
     
		
     while(j<=last) //        ，         
	     b[k++]=a[j++];
    
    
     for(i=first; i<=last;++i)//b   ， a      
        a[i]=b[i];
     return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    int* a=(int*) calloc(n, sizeof(int));//            n    size     
    int* b=(int*) calloc(n, sizeof(int));
    int i=0;
    for(i=0;i<n;++i) //       
        scanf("%d",(a+i));
    
    printf("%lld
",Calc(a,b,0,n-1));
    
    for(i=0;i<n;++i) //       
        printf("%d ",*(a+i));
        
        
    return 0;
} 

4. 해법 --- 병합 법

#include <iostream>
using namespace std;

int a[100], b[100]; // a      ，b        

/*    a[p..q]   a[q+1..r]，        */ 
int merge(long p, long q, long r) 
{ 
   int inv = 0; 
   long i, j = 0; 
   long beginA = p, endA = q, beginB = q+1, endB = r; 
   while(beginA <= endA && beginB <= endB) 
   { 
         if(a[beginA] <= a[beginB]) 
		 { 
            b[j++] = a[beginA++]; 
         }
         else 
		 { 
            b[j++] = a[beginB++]; 
            inv += (q - beginA + 1); //                        
         } 
   } 
   while(beginA <= endA) 
   { 
       b[j++] = a[beginA++]; 
       inv += (r - q); 
   } 
   while(beginB <= endB) 
   { 
       b[j++] = a[beginB++]; 
   } 
   for(i = 0; i < j; i++)
      a[p+i] = b[i]; 

   return inv; 
}


/*   a[first..last]   ，        */ 
int mergeSort(long first, long last) 
{ 
    if (first < last) 
	{ 
        long mid = (first + last) / 2; 
        int inv = mergeSort(first, mid); 
        inv += mergeSort(mid+1, last); 
        inv += merge(first, mid, last); 
        return inv; 
    }
    else
	 
        return 0; 
     
} 


int main()
{    
    a[0]=2;
    a[1]=3;
    a[2]=1;
    a[3]=4;
    int res=mergeSort(0,3); 
	cout<<"res="<<res<<endl;
}