递归求逆序对个数

描述

给定输入n，之后输入1到n的一个排列，求排列中的逆序对的个数；

想法

思路一：

• 找到序列中的最大数（记其下标为i），则前面的所有数都不会和这个数形成逆序，后面的所有数和这个数都是一个逆序对，从而有n-i-1个逆序对；
• 删掉这个数，则剩下的数形成n-1规模的子问题，递归执行；
  用链表存储数据，可以节省删除元素后移动剩余元素的时间，加快执行速度；时间复杂度O(n^2)

思路二：

• 利用归并排序的思想，将问题分解为两个子部分，要求两个子部分有序，然后归并两个子部分，归并过程计算出子部分间的逆序数，返回给上一层函数；
• 递归终止条件是当只有一个数的时候，返回逆序数为0；
• 时间复杂度和归并排序相同，为O(n*logn)

---

思路二代码实现：

#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
//归并，并计算出逆序数的个数
int Merge(int a[],int s,int mid,int e,int b[]){
    int i=s;
    int j=mid+1;
    int k=s;	//k从s开始，把要归并的两段复制到辅助数组b的同样的位置，方便之后存回a
    int count=0;	//逆序数个数
    while(i<=mid && j <=e){
        if(a[i] <= a[j]){
            b[k++]=a[i++];
        }else{
            b[k++]=a[j++];
            count += mid - i + 1;	//a[i]>a[j]时，i到mid所有数都和a[j]形成逆序对
        }
    }
    while(i<=mid){
        b[k++] = a[i++];
    }
    while(j<=e){
        b[k++] = a[j++];
    }
    for(int i=s;i<=e;i++)
        a[i] = b[i];	//归并之后的有序序列存回a
    return count;
}
//求逆序数
int InverseNumber(int a[],int s,int e,int b[]){
    if(s >= e)		//递归终止条件
        return 0;
    int mid = s+(e-s)/2;
    int ret=0;
    //分治，把问题分成两部分，分别求逆序数再归并起来，将结果返回出去
    ret += InverseNumber(a,s,mid,b);	
    ret += InverseNumber(a,mid+1,e,b);
    ret += Merge(a,s,mid,e,b);
    return ret;
}

int main(){
    int ret;
    int n;
    cin >> n;
    const int SIZE = n;
    int a[SIZE],b[SIZE];
    for(int i=0;i<n;i++)
        cin >> a[i];
    ret = InverseNumber(a,0,SIZE-1,b);
    cout << ret << endl;
    return 0;
}