Blog of AgioPan
0%

数据结构与算法自学笔记（6）- 递归、归并排序与归并分治

Posted on Edited on In ,

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

记录的是class020→class022，包括了递归的本质理解、Master公式的应用、归并排序的递归与非递归实现，以及归并分治思想在解决小和问题和翻转对问题中的应用。

020【必备】递归和Master公式

递归的本质理解

思想层面的递归

递归不是玄学，它是一种**”大事化小”**的思维方式。对于新手来说，画调用图是理解递归的关键。

1
2
3
4
5
6
7
8
9
10
11
12
13
def max_value(arr):
    '''给定一个数组，在arr[l...r]范围上，返回最大值'''
    return f(arr, 0, len(arr) - 1)

def f(arr, l, r):
    # arr[l...r] 范围上的最大值
    if l == r:
        # 递归基：当左右下标相等时，区间只有一个数，直接返回
        return arr[l]
    m = (l + r) // 2  # 找到中点
    lmax = f(arr, l, m)        # 递归求左半部分最大值
    rmax = f(arr, m + 1, r)    # 递归求右半部分最大值
    return max(lmax, rmax)     # 返回左右部分的最大值

递归的三个关键点：

  1. 明确递归要干什么：这里是”返回 arr[l…r] 的最大值”
  2. 找递归的终止条件：这里是”l == r”，即区间只有一个数
  3. 思考如何缩小规模：这里是分别递归处理左区间和右区间

实际层面的递归

递归底层利用系统栈来实现：

  • 当函数调用发生时，系统会将函数的状态（参数、局部变量、返回地址）压入栈中
  • 当函数返回时，系统从栈中弹出状态，恢复到调用点继续执行
  • 这个过程是可视化的，所以所有递归函数都可以改成非递归

递归改非递归的必要性：

  • 工程实践：几乎一定要改，除非确定递归深度不会太大
  • 算法竞赛：能通过就不改，时间紧迫时优先保证正确性

形象比喻：

  • 迭代像是擂台赛：一个个来，逐步解决
  • 递归像是季后赛：分组对战，逐层淘汰
    递归过程分步
    递归时的数据结构

Master公式详解

Master公式用于分析分治算法的时间复杂度，适用于所有子问题规模相同的递归。

公式形式

$$T(n) = a \times T(\frac{n}{b}) + O(n^c)$$

其中：

  • a：子问题被调用的次数
  • b：子问题规模（数据量变为原来的1/b）
  • c：除去子问题之外的时间复杂度指数

判断标准

设 $\log_b(a) = d$，则：

条件 时间复杂度 说明
$d < c$ $O(n^c)$ 合并工作量占主导
$d > c$ $O(n^d)$ 递归调用占主导
$d = c$ $O(n^c \log n)$ 两者平衡

经典例子分析

1
2
3
4
5
6
7
8
9
10
# 归并排序：T(n) = 2*T(n/2) + O(n)
# a=2, b=2, c=1
# log₂(2) = 1 = c，所以复杂度为 O(n*logn)

# 二分查找：T(n) = 1*T(n/2) + O(1)  
# a=1, b=2, c=0
# log₂(1) = 0 = c，所以复杂度为 O(logn)

# 快速排序最好情况：T(n) = 2*T(n/2) + O(n)
# 结果同归并排序：O(n*logn)

特殊情况

对于 $T(n) = 2 \times T(\frac{n}{2}) + O(n \log n)$：

  • 这不符合标准Master公式形式，结果是 $O(n \times (\log n)^2)$，需要特殊记忆，证明过程较复杂，这种递归式常见于“分治 + 合并时需要二分/复杂统计”的问题，比如“翻转对”、“区间对统计”，主定理告知其复杂度为 $O(n \log^2 n)$

021【必备】归并排序

归并排序原理

核心思想

  1. 左部分排好序、右部分排好序
  2. 利用merge过程让左右整体有序
  3. merge过程：谁小拷贝谁，直到左右两部分数字耗尽，拷贝回原数组

为什么归并排序比O(n²)排序快？

比较行为没有浪费！

对比三种原始排序（选择、冒泡、插入）：

  • 每次1到N-1次比较只能确定一个位置
  • 大量比较工作被浪费，效率低下

归并排序中：

  • 每次比较都有意义，用于合并两个有序序列
  • 比较结果被充分利用，没有浪费
  • 系统栈不会太深

归并排序的栈不会深
归并排序的栈不会深2

测试链接 ：https://www.luogu.com.cn/problem/P1177

递归实现

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
MAXN = 100001
arr = [0] * MAXN      # 原数组
help_arr = [0] * MAXN # 辅助数组
n = 0                 # 数组长度

def mergeSort1(l, r):
    """
    归并排序递归版
    T(n) = 2 * T(n/2) + O(n)
    根据master公式，时间复杂度O(n * logn)
    空间复杂度O(n)
    """
    if l == r:  # 递归终止条件：只剩一个元素
        return
    m = (l + r) // 2  # 计算中点
    mergeSort1(l, m)      # 递归排序左半部分
    mergeSort1(m + 1, r)  # 递归排序右半部分
    merge(l, m, r)        # 合并

def merge(l, m, r):
    """
    合并两个有序区间 arr[l...m] 和 arr[m+1...r]
    时间复杂度O(n)，其中n = r - l + 1
    """
    i = l      # help数组写指针
    a = l      # 左侧起始指针
    b = m + 1  # 右侧起始指针
    
    # 双指针合并过程
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b] 
            b += 1
        i += 1
    
    # 处理剩余元素
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
        
    # 写回原数组
    for i in range(l, r + 1):
        arr[i] = help_arr[i]

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def mergeSort2():
    """
    归并排序非递归版
    时间复杂度O(n * logn)：外层循环O(logn)，内层归并O(n)
    空间复杂度O(n)
    """
    global n
    step = 1  # 步长初始化为1
    
    while step < n:  # 外层控制步长，共O(logn)次
        l = 0  # 每轮从左端开始
        
        while l < n:  # 内层处理每一组
            m = l + step - 1      # 计算中点
            if m + 1 >= n:        # 右半部分越界，跳出
                break
            r = min(l + (step << 1) - 1, n - 1)  # 计算右边界
            merge(l, m, r)        # 合并
            l = r + 1             # 移动到下一组
            
        step <<= 1  # 步长翻倍

非递归实现的核心思路

  1. step表示每次要合并的有序段长度，初始为1（每个元素自己是有序段）
  2. 每一轮成对合并长度为step的有序段，合并成长度为2*step的有序段
  3. 下一轮step翻倍，继续两两合并
  4. 重复直到step >= n，整个数组有序

过程示例：

1
2
3
4
5
原数组: [3, 8, 7, 6, 4, 5, 1, 2]

step=1: [3,8] [6,7] [4,5] [1,2] → [3,8,6,7,4,5,1,2]
step=2: [3,6,7,8] [1,2,4,5] → [3,6,7,8,1,2,4,5] 
step=4: [1,2,3,4,5,6,7,8] → [1,2,3,4,5,6,7,8]

merge过程详解

双指针合并策略

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
def merge(l, m, r):
    """
    合并过程详解：
    1. 双指针扫描：a指向左部分，b指向右部分
    2. 比较合并：较小值写入help_arr，对应指针右移
    3. 剩余处理：一边扫完后，另一边直接复制
    4. 写回原数组：完成排序合并
    """
    i = l      # help_arr写入位置
    a = l      # 左部分起点
    b = m + 1  # 右部分起点
    
    # 两两比较，选择较小值
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b]
            b += 1
        i += 1
    
    # 处理剩余元素（必有一边先结束）
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
    
    # 拷贝回原数组
    for idx in range(l, r + 1):
        arr[idx] = help_arr[idx]

复杂度分析

时间复杂度：O(n log n)

  • 递归层数：log₂(n)层，每次将问题规模减半
  • 每层工作量：O(n)，所有元素都要参与一次合并
  • 总复杂度：O(n) × O(log n) = O(n log n)

空间复杂度：O(n)

  • 辅助数组：需要与原数组等长的help_arr
  • 递归栈：最大深度O(log n)，但主要空间开销是辅助数组
  • 原地归并：理论上可以做到O(1)空间，但时间复杂度会退化到O(n²)

022【必备】归并分治

归并分治的核心思想

归并分治是在归并排序基础上的拓展，用来解决更复杂的问题。

应用条件判断

一个问题能用归并分治解决，需要满足：

  1. 大范围答案 = 左部分答案 + 右部分答案 + 跨越左右产生的答案
  2. 计算”跨越左右产生的答案”时，左右各自有序能带来计算便利性
  3. 如果以上两点成立，该问题很可能被归并分治解决

求解过程：在归并排序过程中加入统计逻辑，利用左右有序的特性获得计算便利性。

小和问题

问题描述

给定数组arr，对于每个位置i，求出其左边所有小于等于arr[i]的数的累加和，所有位置的累加和即为数组的”小和”。

例子：

1
2
3
4
5
6
7
8
9
10
数组: [1, 3, 5, 2, 4, 6]

位置0(1): 左边小于等于1的数 → 0
位置1(3): 左边小于等于3的数 → 1  
位置2(5): 左边小于等于5的数 → 1+3 = 4
位置3(2): 左边小于等于2的数 → 1
位置4(4): 左边小于等于4的数 → 1+3+2 = 6
位置5(6): 左边小于等于6的数 → 1+3+5+2+4 = 15

小和 = 0+1+4+1+6+15 = 27

分治指针滑动
小和问题拆分成子问题

测试链接 ：https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469

归并分治解法

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
def smallSum(l, r):
    """
    返回arr[l...r]范围上小和的累加和，同时让arr[l..r]变有序
    时间复杂度O(n * logn)
    """
    if l == r:
        return 0
    m = (l + r) // 2
    # 递归统计左右部分和跨区部分的小和
    return smallSum(l, m) + smallSum(m + 1, r) + merge(l, m, r)

def merge(l, m, r):
    """
    统计跨左右产生的小和，同时完成合并
    """
    ans = 0        # 累计小和
    i = l          # 左侧指针
    sum_left = 0   # 累计左侧小于等于当前右侧元素的和
    
    # 统计跨区贡献：对每个右侧元素，统计左侧贡献
    for j in range(m + 1, r + 1):
        # 左侧所有 <= arr[j] 的元素都对arr[j]有贡献
        while i <= m and arr[i] <= arr[j]:
            sum_left += arr[i]  # 累加左侧贡献
            i += 1
        ans += sum_left  # arr[j]的左侧贡献总和
    
    # 正常归并过程
    i = l
    a = l
    b = m + 1
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b]
            b += 1
        i += 1
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
    for idx in range(l, r + 1):
        arr[idx] = help_arr[idx]
    
    return ans

算法关键思路

为什么要在merge过程中统计？

  1. 左右有序的便利性：因为左右都有序，可以用双指针线性扫描
  2. 避免重复计算：每个跨区的小和贡献只需要计算一次
  3. 时间复杂度优势：总体保持O(n log n)，而暴力解法是O(n²)

核心技巧：

  • 对于右半部分的每个元素arr[j]，左半部分所有 ≤ arr[j] 的元素都会对小和产生贡献
  • 由于左半部分有序，可以用指针i从左向右扫描，累加贡献值
  • 指针i只会前进不会后退，总的扫描时间为O(n)

翻转对问题

问题描述

给定数组nums，如果i<j且nums[i]>2*nums[j]，我们就将(i,j)称作一个重要翻转对。求数组中翻转对的总数量。

例子：

1
2
3
数组: [1,3,2,3,1]
翻转对: (1,4)→3>2*1, (3,4)→3>2*1
答案: 2

测试链接 ：https://leetcode.cn/problems/reverse-pairs/

归并分治解法

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
def reversePairs(arr):
    """统计翻转对的主函数"""
    return counts(arr, 0, len(arr) - 1)

def counts(arr, l, r):
    """
    统计l...r范围上翻转对的数量，同时让l...r范围变有序
    时间复杂度O(n * logn)
    """
    if l == r:
        return 0
    m = (l + r) // 2
    # 递归统计左右两边和跨区部分的翻转对数量
    return counts(arr, l, m) + counts(arr, m + 1, r) + merge(arr, l, m, r)

def merge(arr, l, m, r):
    """统计跨区翻转对并完成合并"""
    ans = 0  # 翻转对计数
    j = m + 1  # 右边数组起点
    
    # 统计跨区翻转对
    for i in range(l, m + 1):
        # 找到右侧第一个不满足 arr[i] > 2*arr[j] 的位置
        while j <= r and arr[i] > 2 * arr[j]:
            j += 1
        # 当前i能形成的翻转对数量 = j - (m+1)
        ans += j - m - 1
    
    # 正常merge过程（与归并排序相同）
    i = l
    a = l
    b = m + 1
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b]
            b += 1
        i += 1
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
    for idx in range(l, r + 1):
        arr[idx] = help_arr[idx]
    
    return ans

算法关键思路

统计策略：

  1. 利用左右部分独立有序：对于左半部分的每个元素arr[i]，在右半部分找到满足arr[i] > 2*arr[j]的所有j
  2. 指针单向移动：左右部分都是有序的，指针j只需要前进，不需要回退
  3. 计数技巧：当找到第一个不满足条件的j时，说明j前面的所有元素都满足条件

时间复杂度分析：

  • 每个元素只会被访问一次，总的统计时间：O(n)，符合归并分治的要求

归并分治总结

适用问题特征

  1. 可分解性：问题可以分解为左部分 + 右部分 + 跨区部分
  2. 有序性便利：跨区部分的计算在左右有序时能够优化
  3. 线性合并：跨区计算的时间复杂度为O(n)

解题模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def divide_conquer(l, r):
    if l == r:
        return base_case
    
    m = (l + r) // 2
    left_ans = divide_conquer(l, m)
    right_ans = divide_conquer(m + 1, r)
    cross_ans = merge_and_count(l, m, r)  # 关键：统计跨区答案
    
    return left_ans + right_ans + cross_ans

def merge_and_count(l, m, r):
    # 1. 利用左右有序性，统计跨区答案
    cross_count = 0
    # ... 统计逻辑
    
    # 2. 正常的归并排序merge过程
    # ... 合并逻辑
    
    return cross_count

常见应用

  1. 小和问题：统计左侧小于等于当前元素的累加和
  2. 翻转对问题：统计满足特定大小关系的数对
  3. 最近点对问题：二维空间中最近两点距离（高难度）
  4. 逆序对问题：统计数组中的逆序对数量

与其他算法的关系

  • 线段树：也可以解决类似问题，但常数因子可能更大
  • 树状数组：适合在线查询修改，离线场景下归并分治更简洁
  • 分块算法：另一种分治思想，将在后续课程中介绍

归并分治是一种优雅而强大的算法思想，它将复杂问题通过分治和有序性的结合，优雅地降低了时间复杂度。掌握这种思想对于解决许多看似困难的问题都有很大帮助。