https://www.bilibili.com/video/av11250539?from=search&seid=8977949544767058812 附上一个超有趣的归并排序 动画
https://www.luogu.org/problemnew/show/P1908 题目
1 #include<iostream> 2 #include<cstdio> 3 #include <cctype> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 #include<string> 8 #include<cmath> 9 #include<set> 10 #include<vector> 11 #include<stack> 12 #include<queue> 13 #include<map> 14 using namespace std; 15 #define ll long long 16 #define mem(a,x) memset(a,x,sizeof(a)) 17 #define se second 18 #define fi first 19 const int INF= 0x3f3f3f3f; 20 const int N=1e6+5; 21 22 int n,a[40005],t[40005],ans; 23 24 void merge(int l,int r) 25 { 26 if(l==r) return; 27 int i=l,mid=(l+r)>>1,j=mid+1; 28 merge(l,mid); 29 merge(mid+1,r); 30 31 //接下来是合并 32 int p=l; 33 while(i<=mid && j<=r) 34 { 35 if(a[i]>a[j]) 36 t[p++]=a[j++], ans+= mid-i+1; 37 //此时两边都是排好序了的，当前面的序列中有一个数大于后面的一个数时，前面序列中剩下的数都大于这个数，共mid-i+1个 38 else 39 t[p++]=a[i++]; 40 } 41 while(i<=mid) 42 t[p++]=a[i++]; 43 while(j<=r) 44 t[p++]=a[j++]; 45 46 for(int i=l;i<=r;i++) //还回去 47 a[i]=t[i]; 48 } 49 50 int main() 51 { 52 cin>>n; 53 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 54 ans=0; 55 56 merge(1,n); 57 cout<<ans; 58 }