首页 > 代码库 > 归并排序求逆序对

归并排序求逆序对

归并排序求逆序对

by mps

  【1】什么是逆序对?

      对于一个数列需要按从小到大排序,如果有ai,aj且满足ai>aj和i<j则ai,aj为一组逆序对

  【2】如何求逆序对?

       我们发现,我们可以暴力枚举i,j,然后逐一判断并累加答案即可,时间复杂度O(N2)

       但是对于数据量大一点的题目,只有不断地TLE了→_→

  【3】归并排序求逆序对

       逆序对的定义(见【1】)是一组本应该有序的序列中的逆序对,那么我们就想到了排序,但由于是要22匹配,我们又想到了归并排序

       归并排序大致内容如下:

             将一组数据先不断分割,直到分为一个一组,然后对于每个区间自小到大的进行有序表合并(O(N)),然后向上回溯,主体思想是分治

       我们发现,在合并的时候,如果出现有一组合并错误

(即不是直接A然后紧跟B,而是中间有一个ai并没有在正确的位置,被b中的一个数取代了,那就证明一定有mid-i+1个逆序对,因为前面一定是有序的)

       所以求逆序对本身非常简单,只需要写一个归并排序,在合并的过程中,如果并不是插入了A的元素,而是B的,则答案类加上mid-i+1

  【4】模板

 1 void Union(int l,int mid ,int r){ 2     int i=l,j=mid+1,len=l-1; 3     while(i<=mid && j<=r) 4     { 5         if(a[i]<=a[j])b[++len]=a[i++]; 6         else { 7             b[++len]=a[j++]; 8             ans+=mid-i+1; 9             ans=ans%Mod;10         }11     }12     while(i<=mid)b[++len]=a[i++];13     while(j<=r)b[++len]=a[j++];14     for(i=l;i<=r;i++)a[i]=b[i];15 }16 17 void merge_sort(int l,int r){18     if(l<r){19         int mid=(l+r)>>1;20         merge_sort(l,mid);21         merge_sort(mid+1,r);22         Union(l,mid,r);23     }24 }25 26 int main(){27   init();28   merge_sort(1,n);29   printf("%d",ans);30   return 0;31 }

  【5】总结

    该算法的时间复杂度由O(N2)降至O(NlogN)

    空间复杂度由O(1)升至O(N)

    空间换时间

 

归并排序求逆序对