方法一：暴力

求数组逆序对个数暴力做法时间复杂度$O(n^2)$

方法二：归并排序

如数组9 7 5 4 6，归并排序合并9 7时：由于9比7大，逆序对数加1。合并7 9和5时：7比5大，逆序对数加2。合并4 6时：无逆序对。合并5 7 9和4 6时：5比4大，逆序对数加3，7比6大，逆序对数加2。所以总共逆序对数是8。计算逆序对数时间复杂度$O(n)$，递归层数$logn$，时间复杂度$O(nlogn)$，空间复杂度$O(n)$

需要在求逆序对的时候对数组同时排序，因为如果不排序，合并9 7 5和4 6时就只能暴力计算逆序对数，所以是在归并排序的同时计算出逆序对数

void mergeSort(int *record, int l,int r, int *ans){
    if(l >= r)return;
    int mid = l + r >> 1;
    mergeSort(record, l, mid, ans);
    mergeSort(record, mid + 1, r, ans);
    int temp[r - l + 1], idx = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if(record[i] > record[j]){
            *ans += mid - i + 1;
            temp[idx++] = record[j];
            j++;
        } else {
            temp[idx++] = record[i];
            i++;
        }
    }
    while(i <= mid){
        temp[idx++] = record[i];
        i++;
    }
    while(j <= r){
        temp[idx++] = record[j];
        j++;
    }
    for(int i = 0; i < idx; i++){
        record[l + i] = temp[i];
    }
}
int reversePairs(int* record, int recordSize) {
    int ans = 0;
    mergeSort(record, 0, recordSize - 1, &ans);
    return ans;
}