首页 > 代码库 > 归并排序求逆序对
归并排序求逆序对
归并排序求逆序对
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)
空间换时间
归并排序求逆序对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。