归并排序应用之小和问题

问题描述

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。

举个栗子

{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

代码实现

public class SmallSum {

    public static void main(String[] args) {
        int[] arr = {3,2,1,7,6,8,9,0,5};
        System.out.println(smallSum(arr));
    }
    
    public static int smallSum(int[] arr){
        if(arr==null||arr.length<2){
            return 0;
        }
        return mergeSort(arr,0,arr.length-1);
    } 
    
    public static int mergeSort(int[] arr,int L,int R){
        if(L == R){
            return 0;
        }
        int mid = L + ((R - L)>>1);
        return mergeSort(arr,L,mid)+mergeSort(arr,mid+1,R)+merge(arr,L,mid,R);
    }
    
    public static int merge(int[] arr,int L,int mid,int R){
        int[] help = new int[R-L+1];
        int i = 0;
        int p1 = L;
        int p2 = mid+1;
        int sum = 0;
        while(p1 <= mid && p2 <= R){
            sum += arr[p1] < arr[p2] ? arr[p1]*(R-p2+1) : 0; 
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= R){
            help[i++] = arr[p2++];
        }
        for(i=0;i<help.length;i++){
            arr[L+i] = help[i];
        }
        return sum;
    }
}

上述代码与归并排序的代码多了这个sum += arr[p1] < arr[p2] ? arr[p1]*(R-p2+1) : 0; ，其他的逻辑是完全一样的。

为什么这样求出来的就是小和？
1、将一个数组不断划分，划分成左右两个子集，最终划分为最小子集，两边各一个数的时候划分结束；
2、左右两个数比较，如果左边子集的那个数小于右边子集的那个数，那么就算进小和里面，紧接着会有一个归并排序的排序过程（如果是左边小当然不会发生变化），这样最小子集的数的小和算出来了，也排好序了；然后和这两个数同时划分的另外两个子集中也进行一样的操作，那么另外一侧的小和也算出来了，顺序也排好了（当然一个数就没有可以直接和之前排好的比较，内部就没有排序求小和了）
3、假如说通过2的操作，现在分别是两组内部有两个数的子集，那么又因为这两个子集是同一级（同一次分组形成的），这两个内部数据是有序的，右侧子集的第一个数字和左侧子集的第一个数字比较，如果右侧第一个就比左侧第一个大，那么右侧两个数字都比第一个数字大，则（左侧数字*2）就是此次小和的一部分了（其中2是([右侧子集R]-[右侧第一个数字的下标])+1），然后开始和左侧第二个数字比较，依次下去。这也就是上述多出的那一行代码的逻辑。

上述解释总归是文字，描述上理解上会有出入，拿一组具体的数字来配合上述解释：

归并排序求小和图解.png

end