归并排序-最小和

前面的文章已经讲了归并排序的几种实现，今天来说说通过归并排序来求最小和的问题

首先澄清一下最小和的概念：给定一个数组，对于数组中的每个元素，把它前面所有比它小的元素全部加起来生成一个小和，然后把每个元素对应的小和全部加起来生成整个数组的一个小和，比如给定数组{3, 2, 2, 4, 1, 5}，每个元素对应的小和是{0,0,0,7,0,12}，整个数组的小和就是19

首先我们常规的思路就是两个for循环，简单粗暴，但是时间复杂度不太行(O(N的平方)),也就是下面的代码：

    private int smallSum(int[] array) {
        int length = array.length;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (array[j] < array[i]) {
                    sum += array[j];
                }
            }
        }
        return sum;
    }

那么怎么利用归并排序来实现呢，我们知道归并排序的核心思想是把数组切分成两个子数组进行merge(这两个子数组内部肯定是有序的，至于为什么，去看看归并排序的代码实现就知道了)，分别有两个指针指向每个数组的起始位置，移动指针比较，然后借助一个临时数组拷贝数据，来完成数据的排序，在拷贝数据的时候就有一个很重要的依据：谁小就拷贝谁，于是我们可以考虑从这个地方着手：如果左边数组当前指针指向的数据小于右边的数组当前指针指向的数据，那么就将左边的数组当前指针对应的的数据累加起来并返回累加的结果，但是这里有个很重要的逻辑就是左边的数组当前指针对应的的数据要累加多次，次数就是右边数组当前指针到数组结尾的数据的个数，下面我来解释一下为什么：

就拿题目中的数组{3, 2, 2, 4, 1, 5}来说，我们从另外一个角度来思考，就是对于每一个元素来说，自己在计算最终结果的时候要加几次，这个几次也就是上面提到的累加多次

比如对于3来说，后面比它大的只有后边的4和5，那么3一定会在最终的结果中累加2次，也就是3*2

对于第一个2来说，后面比它大的只有后边的4和5，那么这个2一定会在最终的结果中累加2次，也就是2*2

对于第二个2来说，后面比它大的只有后边的4和5，那么这个2一定会在最终的结果中累加2次，也就是2*2

对于4来说，后面比它大的只有后边的5，那么4一定会在最终的结果中累加1次，也就是4*1

对于1来说，后面比它大的只有后边的5，那么1一定会在最终的结果中累加1次，也就是1*1

对于5来说，后面比它大的没有，那么5一定会在最终的结果中累加0次，也就是5*0

那么最终计算结果的公式就是：3*2+2*2+2*2+4*1+1*1+5*0=19

接下来我们对题目中的数组一步步合并的推演：

第一轮合并：

3,2合并为{2,3}，局部累加和是0，因为左边比右边大

2,4合并为{2,4}，局部累加和是2*1，因为左边比右边小

1,5合并为{1,5}，局部累加和是1*1，因为左边比右边小

第二轮合并：

{2,3}和{2,4}合并为{2,2,3,4}，局部类累加和为2*1+3*1=5，因为左边的数组{2,3}都比比右边的数组{2,4}中的4要小

第三轮合并：

{2,2,3,4}和{1,5}合并为{1,2,2,3,4,5}，局部累加和为2*1+2*1+3*1+4*1=11，因为左边的数组都比右边的数组中的5要小

最终的结果就是：2*1+1*1+2*1+3*1+2*1+2*1+3*1+4*1=19

我们来看代码实现：

private int mergeSort(int[] arr, int start, int end) {
        if (start == end) {
            return 0;
        }
        int middle = start + ((end - start) >> 1);
       //第四处
        return mergeSort(arr, start, middle) +
                mergeSort(arr, middle + 1, end) +
                merge(arr, start, middle, end);
    }

    private int merge(int[] arr, int start, int middle, int end) {
        int i = 0;
        int[] help = new int[end - start + 1];
        int index1 = start;
        int index2 = middle + 1;
        //第一处
        int sum = 0;
        while (index1 <= middle && index2 <= end) {
            //第二处
            sum += arr[index1] < arr[index2] ? arr[index1] * (end - index2 + 1) : 0;
            help[i++] = arr[index1] < arr[index2] ? arr[index1++] : arr[index2++];
        }
        while (index1 <= middle) {
            help[i++] = arr[index1++];
        }
        while (index2 <= end) {
            help[i++] = arr[index2++];
        }
        int length = help.length;
        for (int i1 = 0; i1 < length; i1++) {
            arr[start + i1] = help[i1];
        }
        //第三处
        return sum;
    }

?大伙儿可以看到在上面的代码中与标准的归并排序做法就是多了//标注的四个地方