• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

逆序对与归并排序

开发技术 开发技术 7小时前 2次浏览

逆序对的定义是 对于i<j;a[i]>a[j]我们称 a[i]和a[j]是一对逆序对

如何求逆序对个数,归并排序或者线段树

归并排序方法 代码都是没测试过,不知道会不会报错…

 1 int a[N],b[N];//a是原数组,b是辅助数组,到时候复制回原数组 
 2 int ans=0;
 3 void mergesort(int l,int r)
 4 {
 5     
 6     if(l>=r)return;
 7     int mid=l+r>>1;
 8     mergesort(l,mid);
 9     mergesort(mid+1,r);
10     int pl=l,pr=mid+1,p=l;
11     while(pl<=mid&&pr<=r)
12     {
13         if(pl<=pr)b[p++]=a[pl++];
14         else 
15         {
16             ans+=mid-pl+1;
17             b[p++]=a[pr++];        
18         }
19     }    
20     while(pl<=mid)b[p++]=a[pl++];
21     while(pr<=r)b[p++]=a[pr++];
22     for(int i=l;i<=r;i++)a[i]=b[i];    
23  } 

线段树就是按值域建树,从数组后开始查询有多少个比当前元素小的数,即query(0,i-1),然后让a[i]这个节点++;

好久没写线段树了,不知道有没有错呢…

 1 void update(int x)
 2 {
 3     sum[x]=sum[ls]+sum[rs];
 4 }
 5 void build(int l,int r,int x)
 6 {
 7     if(l==r)return;
 8     int mid=l+r>>1;
 9     build(l,mid,ls);
10     build(mid+1,r,rs);
11 }
12 void modify(int l,int r,int A,int B,int x)
13 {
14     if(A<=l&&B>=r)
15     {
16         sum[x]++;
17         return;
18     }
19     int mid=l+r>>1;
20     if(A<=mid)modify(l,mid,A,B,ls);
21     if(mid<B)modify(mid+1,r,A,B,rs);
22     update(x);
23 }
24 int query(int l,int r,int A,int B,int x)
25 {
26     if(A<=l&&r<=B)return sum[x];
27     int mid=l+r>>1,ans=0;
28     if(A<=mid)ans+=query(l,mid,A,B,ls);
29     if(mid<B)ans+=query(mid+1,r,A,B,rs);
30     return ans;
31 }

 

最后就是今天看到的题,求一个乱序排列,最少交换几次能变升序排列,每次只能相邻交换,答案是逆序对数;

证明,数学归纳法;n为逆序对数

当n=1时显然成立;

假设n=k时结论成立;

当n=k+1时 我们选择在k对逆序对的基础上,在后面造一对逆序对变成k+1对,且对全局无影响;

由上述结论知道对于k+1对逆序对,我们用1步还原后面逆序对而使得全体影响只剩K对逆序对,对k结论成立;从而K+1成立证毕!

 


程序员灯塔
转载请注明原文链接:逆序对与归并排序
喜欢 (0)