在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 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)。
限制：
0 <= record.length <= 50000
方法一：暴力解法（超时）
使用两层 for 循环枚举所有的数对，逐一判断是否构成逆序关系。
from typing import List
class Solution:
def reversePairs(self, nums: List[int]) -> int:
size = len(nums)
if size < 2:
return 0
res = 0
for i in range(0, size - 1):
for j in range(i + 1, size):
if nums[i] > nums[j]:
res += 1
return res
方法二：分治思想（借助归并排序统计逆序数）
说明：理解这个算法需要对「归并排序」比较熟悉。掌握如果编写递归函数，每一次都一分为二拆分数组的子区间，然后在方法栈弹出的时候，一步一步合并两个有序数组，最后完成排序工作。
而计算逆序数就发生在排序的过程中，利用了「排序」以后数组的有序性。
利用「归并排序」计算逆序对，是非常经典的做法；
关键在于「合并两个有序数组」的步骤，利用数组的部分有序性，一下子计算出一个数之前或者之后元素的逆序的个数；
前面「分」的时候什么都不做，「合」的过程中计算「逆序对」的个数；
「排序」的工作是必要的，正是因为「排序」才能在下一轮利用顺序关系加快逆序数的计算，也能避免重复计算；
在代码实现上，只需要在「归并排序」代码的基础上，加上「逆序对」个数的计算，计算公式需要自己在草稿纸上推导。
思想是「分治算法」，所有的「逆序对」来源于 3 个部分：
左边区间的逆序对；
右边区间的逆序对；
横跨两个区间的逆序对。
下面提供两种写法：
1、在第 2 个子区间元素归并回去的时候，计算逆序对的个数（参考代码 2）；
2、在第 1 个子区间元素归并回去的时候，计算逆序对的个数（参考代码 3）。
「归并排序」与「逆序对」是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：
分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题；
治： 划分到子数组长度为 1 时，开始向上合并，不断将 较短排序数组 合并为 较长排序数组，直至合并至原数组时完成排序；
如下图所示，为数组 [7,3,2,6,0,1,5,4] 的归并排序过程。
合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。
class Solution:
def reversePairs(self, record: List[int]) -> int:
def merge_sort(l, r):
# 终止条件
if l >= r: return 0
# 递归划分
m = (l + r) // 2
res = merge_sort(l, m) + merge_sort(m + 1, r)
# 合并阶段
i, j = l, m + 1
tmp[l:r + 1] = record[l:r + 1]
for k in range(l, r + 1):
if i == m + 1:
record[k] = tmp[j]
j += 1
elif j == r + 1 or tmp[i] <= tmp[j]:
record[k] = tmp[i]
i += 1
else:
record[k] = tmp[j]
j += 1
res += m - i + 1 # 统计逆序对
return res
tmp = [0] * len(record)
return merge_sort(0, len(record) - 1)
转链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/622496/jian-zhi-offer-51-shu-zu-