归并排序

时间复杂度:O(nlogn)

void merge_sort(int l,int r)
{
    if(l>=r) return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);

    int p=l,q=mid+1,k=l;
    while(p<=mid&&q<=r){
        if(a[p]<=a[q]) t[k++]=a[p++];
        else{
            t[k++]=a[q++];
            ans+=mid-p+1;
        }
    }
    while(p<=mid) t[k++]=a[p++];
    while(q<=r) t[k++]=a[q++];

    for(int i=l;i<=r;++i) a[i]=t[i];
}
上一篇:快排归并梳理


下一篇:Java-计算8+88+888+......前十项之和