小和问题、逆序对问题_为什么小和问题可以转化成右边比它大

小和问题和逆序对问题是可以用归并排序来实现的。

小和问题：

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

例子：

[1,3,4,2,5]

1左边比1小的数，没有；

3左边比4小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2 = 16

主要思想：

在归并的过程中比较，找出右边元素有多少比左边的元素大。如上面的数组，1右边有4个比1大的，那么1会出现4次。

实现代码（Java）：

package NewCoder;
 
import java.util.Scanner;
 
/**
 * 小和问题
 * 在一个数组中，每一个数左边比当前数小的累加起来，叫做这个数的小和，求一个数组的小和
 */
public class SmallSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] str = sc.nextLine().split(",");
            int[] num = new int[str.length];
            for (int i = 0; i < str.length; i++) {
                num[i] = Integer.parseInt(str[i]);
            }
            int result = smallSum(num);
            System.out.println(result);
        }
        sc.close();
    }
 
    private static int smallSum(int[] num) {
        if (num == null || num.length < 2)
            return 0;
        return mergeSort(num, 0, num.length - 1);
    }
 
    private static int mergeSort(int[] num, int L, int R) {
        //结束条件
        if (L == R) {
            return 0;
        }
        //计算中点位置
        //防止溢出
        int mid = L + ((R - L) >> 1);
        //左边产生的小和+右边陈胜的小和+合并产生的小和就是整个数组的小和
        return mergeSort(num, L, mid) + mergeSort(num, mid + 1, R) + merge(num, L, mid, R);
    }
 
    private static int merge(int[] num, int l, int mid, int r) {
        //辅助数组
        int[] temp = new int[r - l + 1];
        //辅助数组下标
        int i = 0;
        //左半边数组的指针
        int p1 = l;
        //右半边数组的指针
        int p2 = mid + 1;
        //小和
        int res = 0;
        while (p1 <= mid && p2 <= r) {
            //如果左边指向的值小于右边指向的值，那么p1位置的值一定小于p2以后的所有值
            //因为是有序的，这时候产生小和
            if (num[p1]<num[p2]){
                //计算小和
                res = res+num[p1]*(r-p2+1);
                //排序过程
                temp[i++] = num[p1++];
            }else {
                //不产生小和
                res = res+0;
                //排序过程
                temp[i++] = num[p2++];
            }
        }
        //p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
        while (p1 <= mid) {
            temp[i++] = num[p1++];
        }
        //p2没有越界，说明p1越界了
        while (p2 <= r) {
            temp[i++] = num[p2++];
        }
        //将临时数组中的内容拷贝回原数组中
        //（原left-righe范围的内容被复制回原数组）
        for (int j = 0; j < temp.length; j++) {
            num[l + j] = temp[j];
        }
        return res;
    }
}

逆序对问题：

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对。

主要思想：

在归并的过程中比较，找出左边有多少数比右边的数大，有则产生逆序对，打印。

实现代码(Java)：

package NewCoder;
 
import java.util.Scanner;
 
/**
 * 逆序对问题
 * 在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。
 */
public class Reverse {
    public static int count = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String[] str = sc.nextLine().split(",");
            int[] num = new int[str.length];
            for (int i = 0; i < str.length; i++) {
                num[i] = Integer.parseInt(str[i]);
            }
            reverse(num);
            System.out.println(count);
        }
        sc.close();
    }
 
    private static void reverse(int[] num) {
        if (num==null||num.length<2){
            return;
        }
        mergeSort(num,0,num.length-1);
    }
 
    private static void mergeSort(int[] num, int l, int r) {
        if (l==r){
            return;
        }
        int mid = l+((r-l)>>1);
        //打印左边合并产生的逆序对
        mergeSort(num,l,mid);
        //打印右边合并产生的逆序对
        mergeSort(num,mid+1,r);
        //打印整体合并产生的逆序对
        merge(num,l,mid,r);
    }
 
    private static void merge(int[] num, int l, int mid, int r) {
        int[] temp = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = mid+1;
        while (p1<=mid&&p2<=r){
            //如果p1元素大于p2元素，那么左半边元素一定都大于p1元素
            if (num[p1]>num[p2]){
                //p2以后的逆序对元素全部打印出来
                for (int j = p2; j <=r ; j++) {
                    System.out.println(num[p1]+""+num[j]);
                }
                //计算数量
                count+=(r-p2+1);
                temp[i++]=num[p1++];
            }else {
                temp[i++]=num[p2++];
            }
        }
        while (p1<=mid){
            temp[i++]=num[p1++];
        }
        while (p2<=r){
            temp[i++]=num[p2++];
        }
        for (int j = 0; j < temp.length; j++) {
            num[l+j] = temp[j];
        }
    }
}