逆序对问题（分支法）

逆序对（分治法）

逆序对的含义

什么是逆序对？

image-20220504105956937

例如上面这个表格第一行是数组序号，第二行是数组元素

当序号小的数组元素值大于序号大的数组元素值的时候称这两个数为逆序对

例如：

（4,3）（4,5）就是逆序对

枚举法

我们通过两层for循环来遍历这个数组，挨个寻找到所有的逆序对

分治法

我们把数组分为两个部分对每个部分分别求解，使用二分法，对每个部分分别求出最大子序列，然后再求出合并之后的最大子序列，最后让这三部分相加。

image-20220504163411529

最后让这三个相加得出最后的逆序对个数

求解S3的方法：

  1. 使用枚举法，遍历前面的和后面的分别比较求解

    但是最后的时间复杂度还是O(n2n^2)

    image-20220504163710307

    所以直接求解S3的分而治之和蛮力枚举并未提高算法运行时间

    • 原因：我们每次在寻找A[i] 里面那个元素比A[j]的小的时候，都要遍历一遍A[i] ，这样时间比较多
    • 改进方法：我们可以通过讲数组A[i] 和A[j]分别进行排序，然后使用二分查找进行查找对应元素，这样算法效率就能提高不少

  2. 排序之后使用二分法求解

    分别对数组A[1…m]和A[m + 1…n]进行排序
    对于每个A[j] e A[m+ 1…n]，采用二分查找为其在A[1…m]中定位

    A[j]在A[1…m]定位点右侧的元素均可与A[j]构成逆序对
    求解S2S_2 ;的算法运行时间:O(nlogn)
    分治框架的算法运行时间:T(n) = 2T(n/2)+o(nlogn)

    • 可以改进的点：我们没有利用子数组有序的情况，在每次子数组合并之后都要从新排序一下

    • 我们在给子数组排好序之后，在合并子数组的时候应该利用到这个排好序的特性

      image-20220504164657802

      • 优化方法：我们可以在归并的过程同时计算逆序对数目

      image-20220504164800960

算法实例

先二分

image-20220411163845253

后归并

image-20220411163916656

时间复杂度分析

image-20220504164932831

代码实现

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# 逆序对
# 利用分治法和归并排序的原理

def reverse_order_pair(num_array, start, end):
    # 如果只有一个元素的话直接返回就行，自己一个元素逆序对为零
    if start == end:
        return num_array[start:start+1], 0

    # 获取中间元素
    mid = int((end-start)/2 + start)

    # 获取左边元素的逆序对个数
    re_left, num_left = reverse_order_pair(num_array, start, mid)

    # 获取右边元素的逆序对个数
    re_right, num_right = reverse_order_pair(num_array, mid+1, end)
    
    num_reverse = mid_reverse_num(re_left, re_right)
    return re_left, num_reverse + num_left + num_right


# 判断一下两个有序的数组和的逆序对有多少个，并返回合并完之后的数组
def mid_reverse_num(left_array, right_array):
    # 记录一下一共有多少个逆序对
    num_reverse = 0
    
    # 记录一下左边数组和右边数组的下标
    left_num = 0
    right_num = 0

    # 判断一下左边的数组是否走到尽头
    # 判断一下右边的数组是否走到尽头
    while((left_num < len(left_array)) and (right_num < len(right_array))):

        # 如果左边的数组的left_num下标的元素 大于 右边数组的right_num下标的元素
        # 则包右边的元素插入到左边
        if left_array[left_num] > right_array[right_num]:
            # 逆序对个数+1
            num_reverse += (len(left_array) - left_num)

            # 把右边的元素插入到左边数组中，并把调整一下两个数组的下标
            left_array.insert(left_num, right_array[right_num])

            # 为了让左边数组的元素还指向原先的数据
            left_num += 1
            # 让右边的元素指向后边的一个元素
            right_num += 1
        else:
            # 让左边的元素指向后面一个元素 
            left_num += 1
    
    if left_num == len(left_array):
        left_array.extend(right_array[right_num:len(right_array)])
    elif right_num != len(right_array):
        num_reverse += (len(left_array)-left_num-1)
    return num_reverse
    

X = [13,8,10,6,15,18,12,20,9,14,17,19]


array, num = reverse_order_pair(X, 0, len(X)-1)

print(num)
print(array)