「分治算法」三步走

「分治算法」三步走

主要思想

---

分治算法，即分而治之：把一个复杂问题分成两个或更多的相同或相似子问题，直到最后子问题可以简单地直接求解，最后将子问题的解合并为原问题的解。归并排序就是一个典型的分治算法。
在这篇文章中我们将先介绍分治算法的「三步走套路」，然后通过经典的归并排序算法体验一番分治算法的核心，最后再通过真题演练一试身手！

三步走

---

和把大象塞进冰箱一样，分治算法只要遵循三个步骤即可：分解 -> 解决 -> 合并。
1.分解：分解原问题为结构相同的子问题（即寻找子问题）
2.解决：当分解到容易求解的边界后，进行递归求解
3.合并：将子问题的解合并成原问题的解

分治算法三步走

这么一说似乎还是有点抽象？那我们通过经典的排序算法归并排序来体验一下分治算法的核心思想。

归并排序

---

思想

归并排序的思想是：欲使序列有序，必先使其子序列有序。即先使得每个子序列有序，然后再将子序列合并成有序的列表。
因此，在归并排序中的子问题就是：使子序列有序。

三步走

既然已经找到了问题的子问题，是时候套用我们上述的三步走方法了。归并排序的「三步走」如下：
1.分解：将序列划分为两部分
2.解决：递归地分别对两个子序列进行归并排序
3.合并：合并排序后的两个子序列

举例

来看一个具体的例子。
现在有一个待排序的序列：

10, 4, 6, 3, 8, 2, 5, 7

先对序列进行分解，把该序列一分为二，直到无法拆分为止。整个拆分过程如下：

序列分解

然后对分解出的序列进行两两排序与合并：

10, 4 排序合并后：4, 10
6, 3 排序合并后：3, 6
8, 2 排序合并后：2, 8
5, 7 排序合并后：5, 7
……

整个归并排序完整过程如下：

上部分为「分解」，下部分为「解决」与「合并」

实现

def merge_sort(lst):
    # 从递归中返回长度为1的序列
    if len(lst) <= 1:
        return lst          

    middle = len(lst) / 2
    # 1.分解：通过不断递归，将原始序列拆分成 n 个小序列
    left = merge_sort(lst[:middle])     
    right = merge_sort(lst[middle:])
    # 进行排序与合并
    return merge(left, right)

def merge(left, right):
    i, j = 0, 0
    result = []
    # 2.解决：比较传入的两个子序列，对两个子序列进行排序
    while i < len(left) and j < len(right):  
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 3.合并：将排好序的子序列合并
    result.extend(left[i:])         
    result.extend(right[j:])
    return result

总结

---

分治算法的核心是寻找子问题的解，解题步骤遵循「三步走」：
1.找到子问题并分解
2.解决子问题（递归）
3.合并子问题的解

参考资料

---

• OI Wiki: 递归 – 分治：https://oi-wiki.org/basic/divide-and-conquer/

来源 | 五分钟学算法
作者 | 江子抑