求序列逆序数

求序列逆序数

整体思路是用到分治的思想，其实该问题可以在归并排序过程中解决，因此该题代码只需要在归并排序代码上增加一个变量记录逆序数即可，但正如那个修机器的故事一样，换钉子不难，但知道在哪里换钉子却是非常关键。
代码如下，只是在归并排序的基础上增加了一个记录逆序数的地方
void reverse(int num[],int left,int right)//跟归并排序一样
{
int mid;
if(right-left+1>1)//当序列长度大于一时，分成两半进行归并
{
mid= (left+right)/2
reverse(num,left,mid);
reverse(num,mid+1,right);
merge(num,left,right,(left+right)/2);
}
}
void merge(int a[],int left,int right,int mid)//归并过程
{
int i,j,k;
int temp[right-left+1];
for(i=left,j=mid+1,k=0;k<right-left+1;k++)
{
if(a[i]<=a[j]&&i<mid+1)
{
temp[k]=a[i++];
}
else if(a[i]>a[j]&&j<=right)
{
temp[k]=a[j++];
cnt+=mid-i+1;//逆序数增加，增加数为前序列的剩余项
}
else if(i==mid+1)
{
temp[k]=a[j++];
}
else if(j>right)
{
temp[k]=a[i++];
}

}
for(i=0;i<right-left+1;i++)
{
a[left+i]=temp[i];
}

}
两个有序序列，在归并比较过程中，如果后序列元素小，说明前序列包括当前项在内的剩余项均大于后序列的当前项，此时逆序数就增加了前序列的剩余项数。

需要理解的一点时，归并排序过程中，当二分到长度只有一时，序列就是有序的了，然后再进行归并，产生更长的有序序列。