归并排序
归并排序,是将区间分为两部分,先对小的区间进行排序,然后再合并到大的区间中,最后实现全部排好序。
#include<bits/stdc++.h> using namespace std; int a[100010],temp[100010]; void merge(int L,int R){ //对区间进行划分成前两半和后两半 int mid=(L+R)>>1; int k=1,l=L,r=mid+1; while(l<=mid&&r<=R){ if(a[l]<=a[r]) temp[k++]=a[l++]; else{ //这里可以用来求逆序对 sum+=(mid-l+1) temp[k++]=a[r++]; } } while(l<=mid) temp[k++]=a[l++]; while(r<=R) temp[k++]=a[r++]; for(int i=L,k=1;i<=R;i++,k++){ a[i]=temp[k]; } } void mergesort(int l,int r){ if(l<r){ //注意这里的条件 int mid=(l+r)>>1; mergesort(l,mid); mergesort(mid+1,r); merge(l,r); } } int main(){ int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; mergesort(0,n-1); for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }