Peter算法小课堂—归并排序

位运算

<<

这个符号相当于将一个数二进制往左移动几位，如(100110)2<<1=(001100)2。相当于乘以2的k次方

>>

这个符号相当于将一个数二进制往右移动几位，如(100110)2<<1=(0100110)2。相当于除以2的k次方

归并排序

先看一个视频一分钟了解"归并排序"_哔哩哔哩_bilibili

main函数

int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>x[i];
	msort(0,n-1);
	for(int i=0;i<n;i++) cout<<x[i];
	return 0;
}

 这个我相信大家不看就知道怎么写吧

msort函数

msort函数的意义是“对数组l号到r号排序”

思考五分钟：代码该如何填呢

void msort(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	msort(l,mid);
	msort(mid+1,r);
	*************************************************
	*												*
	*		将左右已经排序的两个部分合并			    *
	*												*
	*************************************************	 
}

我们可以使用双游标，给出代码和注释

void msort(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	msort(l,mid);
	msort(mid+1,r);
	int i=l,j=mid+1;//双游标
	for(int k=l;k<=r;k++){
		if(i>mid) y[k]=x[j++];//如果左部分用完，填上右部分当前数 
		else if(j>r) y[k]=x[i++];//如果右部分用完，填上左部分当前数
		else if(x[i]<=x[j]) y[k]=x[i++];//如果左部分当前数小于右部分当前数，填上左部分当前数 
		else y[k]=x[j++];//否则填上右部分当前数 
	} 
}

分析一下时间复杂度

但是，我们发现这个算法空间复杂度不行啊，但是我们不用管他，因为这个算法是稳定排序

逆序对问题

树状数组

#include <bits/stdc++.h>
using namespace std;
int tree[500010],ranks[500010],n;
long long ans; 
struct point
{
    int num,val;
}a[500010];
inline bool cmp(point q,point w)
{
    if(q.val==w.val)
        return q.num<w.num;
    return q.val<w.val;
}
inline void insert(int p,int d)
{
    for(;p<=n;p+=p&-p)
        tree[p]+=d; 
}
inline int query(int p)
{
    int sum=0;
    for(;p;p-=p&-p)
        sum+=tree[p];
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].val),a[i].num=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
        ranks[a[i].num]=i;
    for(int i=1;i<=n;i++)
    {
        insert(ranks[i],1);
        ans+=i-query(ranks[i]);
    }
    printf("%lld",ans);
    return 0;
} 

此处不细讲

归并排序

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=10000009;
int n,x[N],y[N];
ll solve(ll l,ll r){
	if(l==r)return 0;
	ll mid=(l+r)>>1;
	ll ret=0;
	ret+=solve(l,mid);
	ret+=solve(mid+1,r);
	ll i=l,j=mid+1;
	for(ll k=l;k<=r;k++){
		if(i>mid)y[k]=x[j++];
		else if(j>r)y[k]=x[i++];
		else if(x[i]<=x[j])y[k]=x[i++];
		else {ret+=mid-i+1;y[k]=x[j++];}
	}
	for(ll k=l;k<=r;k++)x[k]=y[k];
	return ret;	
}
int main(){
	int cnt=0;
	cin>>n;
	for(ll i=0;i<n;i++)cin>>x[i];
	cout<<solve(0,n-1)<<endl;
	return 0;
}

希望这些对大家有用，三联必回