求一个数列的逆序数
逆序对：数列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
