2.2 分治算法

2.2.1 什么是分治算法

分治法的设计思想：

将难以直接解决的大问题分解成一些规模较小的相同问题，请注意这个相同，以便与动态规划进行区别使用。 分治算法的基本步骤：

分解（Divide）： 将原始问题分解为多个相同或相似的子问题。这一步通常涉及将问题划分成更小的规模，以便于处理。 解决（Conquer）： 逐个解决每个子问题。对于小规模的子问题，可以直接求解。 合并（Combine）： 将各个子问题的解合并，得出原始问题的解。这一步确保子问题的解能够有效地组合成原始问题的解。

2.2.2 分治算法的适用场景

分治算法适用于：

问题可以被分解为更小的相同或相似的子问题进行求解的场景

一些常见的应用场景包括：

• 归并排序（Merge Sort）：归并排序是一种经典的排序算法，它利用了分治思想。该算法将一个大的排序问题分解为多个小的排序子问题，分别解决后再将它们合并起来，得到整体有序的结果。

• 快速排序（Quick Sort）：快速排序也是一种常见的排序算法，同样基于分治思想。它通过选取一个基准元素，将数组划分为两个子数组，然后分别对这两个子数组进行排序，最终得到有序结果。

• 最大子数组和问题：这个问题要求在一个整数数组中找到一个连续的子数组，使得子数组的元素和最大。分治算法可以将问题分解为三种情况：最大子数组在左边、最大子数组在右边，或者跨越了数组中点。然后，将这三种情况的解合并，得到全局最优解。

2.2.3 分治算法模板

2.2.4 分治算法详解

1.归并排序

2.快速排序

快排思想：

• 以第一个元素为中枢，中枢左边元素要小于中枢，中枢右边元素要大于中枢。
• 使用双指针，low指针遇到第一个大于中枢值则停止，hign指针遇到第一个小于中枢值则停止，交换两者位置，之后继续遍历，直到low >= hign。
• 递归左右两边。

3.最大子数组和