一、题目来源：leetcode LCR 170. 交易逆序对的总数

题目描述：

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1：

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

二、题目分析

这道题目来看可以是用O（n²）的遍历求，但是如果是这样，就不会是困难的题目来了，那么对于这种求子集合的方法，初步就是想到用分治的思想，那么就是把数组分到最后的两两数据进行对比，所以就会使用到递归来进行对问题的分解，那么我们只需要考虑左右两部分数据，左边是之前天数的，右边是后面天数的，存在左边天数比右边天数老，所以，我们只需要比较右边有多少天数少于左边天数的，那么就是把里两边的指针数据进行对比，先将两边数组从小到大的排序（这个排序过程就是归并排序）

「归并排序」是分治思想的典型应用，它包含这样三个步骤：

分解： 待排序的区间为 [l,r]，令 m=⌊2l+r​⌋，我们把 [l,r] 分成 [l,m] 和 [m+1,r]

解决： 使用归并排序递归地排序两个子序列

合并： 把两个已经排好序的子序列 [l,m] 和 [m+1,r] 合并起来

在待排序序列长度为 1 的时候，递归开始「回升」，因为我们默认长度为 1 的序列是排好序的。

三、代码实现

package com.caicode.Day02;

public class SmallSum {
    public int FindSmallSum(int[] arr){
        if(arr == null || arr.length < 2 ){
            return 0;
        }
        return process(arr,0,arr.length-1);
    }

    private int process(int[] arr, int l, int r) {
        if(l == r){
            return 0;
        }
        int mid = l + ((r-l) >> 1);
        //将数组分为左右两部分，分别进行递归,归并返回答案
        return process(arr,l,mid) + process(arr,mid+1,r) + merge(arr,l,mid,r);
    }

    private int merge(int[] arr, int l, int mid, int r) {
        //辅助数组，用于对每次递归排序后的数组进行存储
        int[] help = new int[r-l+1];
        int i = 0;
        int sum = 0;
        int p1 = l;
        int p2 = mid + 1;
        while(p1 <= mid && p2 <= r){
            //如果左边的数大于右边的数，则说明整个左边数组都大于这个数，所以整个左边数据个数都要加上
            sum+= arr[p1] > arr[p2] ? (mid-p1+1) : 0;
            //将两个数组进行归并,从小到大，一样的话就吧右边的先放进来
            help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
        }
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        while(p2 <= r){
            help[i++] = arr[p2++];
        }
        //将辅助数组中的数据放回原数组中
        for (int j = 0; j < help.length; j++) {
            arr[l+j] = help[j];
        }
        return sum;

    }


    public static void main(String[] args) {
        int[] arr = {9,7,5,4,6};
        System.out.println(new SmallSum().FindSmallSum(arr));
    }
}

四、结尾

这道题其实容易遗漏的就是为什么要对数组进行从小到大的排序，个人理解，在使用分治进行比较的时候，通过这种O（1）的数据操作实现性能优化，也就是通过数组的下标就可以实现统计个数，不用再遍历数组获得个数，就是正好利用了归并排序的比较，直接进行了逆序对个数的统计，也是比较巧妙的。