归并排序的相关题目(小和问题)

小和

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组
的小和。求一个数组的小和。例子:[1,3,4.2.5] 1左边比1小的数，没有: 3左边比3小的数，1; 4左边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、2;所以小和为1+1+3+1+1+3+4+2=16

转换下思路：我们求一个数右边有多少个数比它大，就产生多少个此数的小和。这样就可以用归并排序。
完整代码

function merge(arry,left,mid,right){
    let size=right-left+1;
    let help=new Array(size);
    let p1=left;
    let p2=mid+1;
    let i=0;
    let result=0;
    while(p1<=mid && p2<=right){
        //merge 时产生小和
        result+=arry[p1]<arry[p2]?(right-p2+1)*arry[p1]:0;
        help[i++]=arry[p1]<arry[p2]?arry[p1++]:arry[p2++];

    }
    while(p1<=mid){
        help[i++]=arry[p1++];
    }
    while(p2<=right){
        help[i++]=arry[p2++];
    }
    for(let j=0;j<help.length;j++){
        arry[left+j]=help[j];
    }
    return result;
}

function sort(arry,left,right){
    if(left === right){
        return 0;
    }
    let mid = left + Math.floor((right - left) / 2);
    return sort(arry, left, mid)+sort(arry, mid + 1, right)+merge(arry, left, mid, right);
}
let a = [1,3,4,2,5];

let sum=sort(a,0,a.length-1);
console.log(sum);

其实只是在归并排序的基础上，增加了求小和的代码。

注意：

1.在有相同的数时，一定要拷贝右边的数，如果拷贝左边，小和数量就不对了。
2.右边（右侧比）必须是排好序的，因为我们要用右侧下标来计算有几个小和（right-p2+1）。

归并排序的相关题目(小和问题)

原文：https://www.cnblogs.com/My-Coding-Life/p/14808352.html