1. 逆序对
假设 A 为一个有 n 个数字的序列 (n > 1)，其中所有数字可以完全不相同，也可以存在相同。如果存在正整数 i, j 使得 0 ≤ i < j ≤ n - 1 而且 A[i] > A[j]，则 (A[i], A[j]) 这个有序对称为 A 的一个逆序对，也称作逆序数。比如：
输入的序列为： 5 1 1 4 2 3
逆序对有： (5,1)、 (5,1)、(5,4)、(5,2)、(5,3)、(4,2)、(4,3)
2. 计算逆序对
逆序对数目发求法主要有以下两种：暴力法和归并法。下面就详细说下这两种方法的解题思想以及具体的实现代码。
2.1 暴力法
（1）暴力法的思想是通过两重循环来枚举所有的有序对，然后求出逆序对的数目。因此，暴力法的时间复杂度为O(N2)，空间复杂度为O(1)。
（2）暴力法的Python代码实现如下：1
2
3
4
5
6
7
8
9def count_reversepair(nums):
# nums为输入的数字序列
count = 0
for i in range(len(nums)):
# 第二重循环注意是从 i+1 开始
for j in range(i+1, len(nums)):
if nums[i] > nums[j]:
count += 1
return count
2.2 归并法
（1）归并法则是利用归并排序的思想来求解逆序对的数目，归并排序的详细过程就不具体说了，简言之就是：先将原序列拆分为左、右子序列，直至不可再拆分，然后将左、右子序列进行有序合并，直到整个序列都合并完。而计算逆序对的过程，就在有序合并这个步骤中，比如上面的例子 nums=[5, 1, 1, 4, 2, 3]：
a. 在最后一次有序合并步骤中（注意前面的已经排好序了），左子序列为left_nums=[1, 1, 5]，右子序列为right_nums=[2, 3, 4]；
b. 然后设置left_begin、left_end为left_nums的开始位置和结束位置，设置right_begin、right_end为right_nums的开始位置和结束位置;
c. 然后循环遍历left_nums和right_nums：
· 如果left_nums[left_begin] > right_nums[right_begin]，说明左边最小值大于右边最小值，即左边所有值都能与右边最小值构成逆序对，此时left_begin往右遍历；
· 否则right_begin往右遍历，继续比较left_nums[left_begin]和right_nums[right_begin]，直到某一边遍历完结束。
归并法利用了归并排序的思想，故其时间复杂度为O(NlogN)，空间复杂度为O(N)。
（2）归并法的Python代码实现如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50def merge(nums, left_begin, left_end, right_begin, right_end, count):
# 最后拷贝回 nums 的起始位置
nums_begin = left_begin
# 用来存储排序后的结果
sorted_list = [0] * (right_end - left_begin + 1)
i = 0
while left_begin <= left_end and right_begin <= right_end:
# 发现逆序对，如果左边最小值大于右边最小值，则左边所有值都能构成逆序对
if nums[left_begin] > nums[right_begin]:
count += (left_end - left_begin + 1)
sorted_list[i] = nums[right_begin]
right_begin += 1
else:
sorted_list[i] = nums[left_begin]
left_begin += 1
i += 1
# 左边有剩余未参与比较的
while left_begin <= left_end:
sorted_list[i] = nums[left_begin]
left_begin += 1
i += 1
# 右边有剩余未参与比较的
while right_begin <= right_end:
sorted_list[i] = nums[right_begin]
right_begin += 1
i += 1
# 最后将 sorted_list 拷贝回 nums 中
for num in sorted_list:
nums[nums_begin] = num
nums_begin += 1
# 归并思想求逆序对
def merge_sort(nums, begin, end, count):
if begin >= end:
return
mid = (begin + end) // 2
# 拆分左、右子序列
merge_sort(nums, begin, mid, count)
merge_sort(nums, mid+1, end, count)
# 有序合并
merge(nums, begin, mid, mid+1, end, count)
##########################################################
# nums = [5, 1, 1, 4, 2, 3]
# cnt = 0
# merge_sort(nums, 0, len(nums) - 1, cnt)
# print(cnt) # cnt 就是逆序对数目
##########################################################
...
...