求逆序数

求一个数列的逆序数

逆序对：数列a[1],a[2],a[3]…中的任意两个数a[i],a[j] (i<j)，如果a[i]>a[j],那么我们就说这两个数构成了一个逆序对

逆序数：一个数列中逆序对的总数

如：数列[3 5 4 8 2 6 9] (3,2),(5,2),(4,2),(5,4)等等都是一个逆序对,设计一个程序求得一个数列的逆序数。（要求时间复杂度为O（nlogn））

主要思路

1、想到时间复杂度为O（nlogn），因此不能按照传统方法“一对一”进行查找
2、O（nlogn）的时间复杂度可以采用归并排序进行协助查找
3、对于序列a1中的某个数a1[i],序列a2中的某个数a2[j]，如果a1[i]<a2[j],没有逆序数，如果a1[i]>a2[j]，那么逆序数为a1中a1[i]后边元素的个数(包括a1[i])，即length1-i+1(下面代码中length1的值等于mid)
4、累加递归过程中的所有逆序数

主要代码

void Merge( int *a, int *b, int left, int right)
 //合并 a[ left:(left+right)/2 ] 和 a[ (left+right)/2+1:right ] 到 b[ left:right ]
 {
int i = left,  m = (left+right)/2, k = left, j = m + 1;
while( (i <= m) && (j <= right) )
    if( a[ i ] <= a[ j ]) b[ k++ ] = a[ i++ ];
    else {
        b[ k++ ] = a[ j++ ];
        count+=m-i+1; //关键代码，归并算法加此代码可求逆序数。
    } 
if ( i>m ) 
    for( int q=j; q<=right; q++ )   b[ k++ ] = a[ q ];
else 
    for( int q=i; q<=m; q++)   b[ k++ ] = a[ q ];
}//将元素进行排序并将排序后的元素合并到数组b中，其中求出逆序数

//分治法解决问题
void MS (int *a, int left, int right) {
    int b[99];
    if (left == right) return ;
    int mid = (left + right)/2;
    MS (a, left, mid);//对左边进行排序（分）
    MS (a, mid+1, right);//对右边进行排序（分）
    Merge (a, b, left, right);//（治， 并）
    copy (a, b, left, right);//将数组b的元素复制到数组a中
}

ps：count+=m-i+1; //关键代码，归并算法加此代码可求逆序数。

完整代码

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int count = 0;
/*
void MG (int *a, int *b, int left, int right) {
int i, j, m, k = left;
i = left;
m = (left+right)/2;
j = m + 1;
while ((i<=m)&& (j<=right)) {
    if (a[i] <= a[j]) {
        b[k] = a[i]; 
        i++; k++;
    }
    else {
        b[k] = a[j]; 
        j++; k++;
    } 
}
if (i>m) {
    while (j<=right) {
        b[k] = a[j];
        k++; j++;
    }
}
else {
    while (i<=m) {
        b[k] = a[i];
        k++; i++;
    }
}
}
*/

void Merge( int *a, int *b, int left, int right)
 //合并 a[ left:(left+right)/2 ] 和 a[ (left+right)/2+1:right ] 到 b[ left:right ]
 {
int i = left,  m = (left+right)/2, k = left, j = m + 1;
while( (i <= m) && (j <= right) )
    if( a[ i ] <= a[ j ]) b[ k++ ] = a[ i++ ];
    else {
        b[ k++ ] = a[ j++ ];
        count+=m-i+1; //关键代码，归并算法加此代码可求逆序数。
    } 
if ( i>m ) 
    for( int q=j; q<=right; q++ )   b[ k++ ] = a[ q ];
else 
    for( int q=i; q<=m; q++)   b[ k++ ] = a[ q ];
}

void copy (int *a, int *b, int left, int right) {
    while (left <= right) {
        a[left] = b[left];
        left ++;
    }
}

void MS (int *a, int left, int right) {
    int b[99];
    if (left == right) return ;
    int mid = (left + right)/2;
    MS (a, left, mid);
    MS (a, mid+1, right);
    //MG (a, b, left, right);
    Merge (a, b, left, right);
    copy (a, b, left, right);
}

int main(int argc, char const *argv[])
{
    int n, left, right;
    int a[99];
    cin >> n;
    for (int i=0; i<n; i++) 
        cin >> a[i];
    left = 0; right = n-1;
    MS (a, left, right);
    cout << count;
    return 0;
}

Example

4
4 3 2 1 enter

输出结果：
6