【算法设计】求逆序数

一，定义

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。

　　也就说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

二，求解方法 --- 暴力求解

时间复杂度 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\n",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\n",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\n",Calc(a,b,0,n-1));
    
    for(i=0;i<n;++i) //输入数字序列 
        printf("%d ",*(a+i));
        
        
    return 0;
} 

四，求解方法 --- 归并法

#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;
}