求逆序数的nlog(2*n)复杂度算法

求逆序数的nlog(2*n)复杂度算法

 求逆序数的nlog(2n)复杂度的算法，其实就是归并排序的原理。只需要在排序的过程中记录一下交换得次数。稍微处理一下就可以了。

   这种算法其实是一种动态规划的算法。运用了分治策略，将大问题化作一个个小问题。例如将数组a[]分成b[],c[],左右两个部分。逆序数的个数就是左数组中逆序数的个数和右数组逆序数的个数，然后将两个数组合并的时候，注意一下左边的数组有多少个数比右边的数组的多少数值要大。

   计数的大体过程是这样的：将数组a[]分成了left--mid,mid-right两部分。取用一个数组c[],记录排好序的数组a[]中left--right之间的部分。

   for (i=left,j=right;i

   {

        if (a[i] > a[j])           //存在逆序数

        {

            c[tmp++] = a[j++];

            cnt += mid - i;        //因为在左边数组中有mid-i个数要比a[j]大

         }

    }

    if (i

    else        for(;j

    以上就是求逆序数的关键部分，以下给出归并排序和记录求逆序数的原代码：

void MergeSort(int l,int r){
     int mid,i,j,tmp;

     if (r>l+1)
     {
         mid = (l+r)/2;
         MergeSort(l,mid);
         MergeSort(mid,r);
         tmp = l;

         for (i=l,j=mid;i         {

             if (a[i]>a[j])
             {
                 c[tmp++] = a[j++];
                 cnt+=mid-i;
             }
             else  c[tmp++] = a[i++];
         }
         if (j         else  for (;i

         

         for (i=l;i             a[i] = c[i];
     }
}