求逆序数的nlog(2n)复杂度的算法，其实就是归并排序的原理。只需要在排序的过程中记录一下交换得次数。稍微处理一下就可以了。
这种算法其实是一种动态规划的算法。运用了分治策略，将大问题化作一个个小问题。例如将数组a[]分成b[],c[],左右两个部分。逆序数的个数就是左
数组中逆序数的个数和右数组逆序数的个数，然后将两个数组合并的时候，注意一下左边的数组有多少个数比右边的数组的多少数值要大。
#include <iostream>
#include <limits>
using namespace std;
/* ////////////////////////////////////////////////////////////////////////// */
int cnt = 0;
int c[100];
void Merge(int a[], int le, int mid, int rh);
void MergeSort(int a[], int le,int rh){
if (rh>le)
{
int mid = (le+rh)/2;
MergeSort(a,le,mid);
MergeSort(a,mid + 1,rh);
Merge(a,le, mid, rh);
}
}
void Merge(int a[], int le, int mid, int rh)
{
int i, j,
tmp = 1;
for (i=le,j=mid+1; i<=mid&&j<=rh; )
{
if (a[j]<a[i])
{
c[tmp++] = a[j++];
cnt+=mid-i+1;//*******important ******//
}
else c[tmp++] = a[i++];
}
if (j<=rh)
for (;j<=rh;++j)
c[tmp++] = a[j];
else
for (;i<=mid;++i)
c[tmp++] = a[i];
for (i=le;i<=rh;++i)
{
a[i] = c[i-le+1];
//cout << a[i] << " " ;
}
}
void main(void)
{
int a[8] = {0, 5,4,3,2,1,0};
//int b[5] = {0, 4,5,2,3};
MergeSort(a, 1,6);
for (int i = 0; i < 5; ++i)
{
std::cout << a[i] << " " ;
}
std::cout <<std::endl << cnt << std::endl;
}
posted on 2008-03-06 15:08
RUI 阅读(1317)
评论(0) 编辑 收藏 引用