归并排序和求逆序对

一个归并排序的代码

#include<iostream>
using namespace std;
int a[500005],r[500005];
void pai(int s,int e)
{if(s==e) return;//小到只有一个数时就不要分了 int mid=(s+e)/2;pai(s,mid);pai(mid+1,e);//二分 把数组一步步变小 直到分为一个个的 int i=s,j=mid+1,k=s; while(i<=mid&&j<=e)//左右都从起点开始 {if(a[i]<=a[j])  r[k++]=a[i++];elser[k++]=a[j++];//把小的数放入r数组中 直到左右俩边有一边没有数（放完了） }while(i<=mid) r[k++]=a[i++];while(j<=e)r[k++]=a[j++];//把没放完的一边的数放入r数组的末尾 for(int i=s;i<=e;i++)a[i]=r[i];//把r数组的数复制到a数组中 
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];pai(1,n);//让数组a从1到n排序 for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
}

用归并排序求逆序对：

#include<iostream>
using namespace std;
int a[500005],r[500005],ans;
void pai(int s,int e)
{if(s==e) return;//小到只有一个数时就不要分了 int mid=(s+e)/2;pai(s,mid);pai(mid+1,e);//二分 把数组一步步变小 直到分为一个个的 int i=s,j=mid+1,k=s; while(i<=mid&&j<=e)//左右都从起点开始 {if(a[i]<=a[j])  r[k++]=a[i++];else{r[k++]=a[j++];//把小的数放入r数组中 直到左右俩边有一边没有数（放完了） ans+=(mid-i+1);//ans即为逆序对个数}}while(i<=mid) r[k++]=a[i++];while(j<=e)r[k++]=a[j++];//把没放完的一边的数放入r数组的末尾 for(int i=s;i<=e;i++)a[i]=r[i];//把r数组的数复制到a数组中 
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];pai(1,n);//让数组a从1到n排序 for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<ans<<endl;//逆序对个数return 0;
}