题目描述
分治的思想:
在归并时,基于两个有序序列的前提下
碰到左边的序列中出现一个数大于右边的数时,由于左边序列的下标值必然小于
右边序列的下标值且左边序列有序,即左边的某个数后面的数必然大于此数
此时可以得到从这个数开始,一直到左边序列结束时的数字个数均满足逆序.
即mid-i+1
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r) {
if(l>=r) return 0 ;
int mid = l+r>>1;
LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
int i=l,j=mid+1;
int k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j])
tmp[k++]=q[i++];
else {tmp[k++]=q[j++]; res+=(mid-i+1);}
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
return res;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
cout << merge_sort(a, 0, n - 1) << endl;
return 0;
}