分治法的设计思想
将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各
个击破，分而治之。如果规模为 n 的问题可分解成 k 个子问题(1<k<=n)，这些
子问题互相独立且与原问题相同。递归的求解这些问题，然后将子问题的解合
并得到原问题的解。能够利用分治法求解的问题，应同时满足如下 4 点要求：
(1)原问题在规模缩小到一定程度时可以很容易的求解。
(2)原问题可以分解为若干个规模较小的同构子问题。
(3)各个子问题的解可以合并为原问题的解。
(4)原问题所分解出的各个子问题之间是相互独立的。
分治法的应用
1. 折半搜索
折半搜索的最大特点是搜素数列有序。用待搜索的对象与数列的中间元素
进行比较。如果比中间元素小，则该数可能在左半部分；如果比中间元素大，
则该数可能在右半部分；如果正好等于，则查找成功；如果最后都没有找到，
则表示数列中不存在此数。这样每次取一半，最多需要进行 log
2
n 次比较就能得
出结果。所以，在最坏情况下，折半搜索算法的时间复杂度为 O(log
2
n)。
2. 归并排序
(1)问题的描述
归并(Merge)就是将多个已经部分有序的数列合并成一个完整的有序数列。
其中，每次操作都是将两个有序序列合并为一个有序序列的归并称为二路归并，
它是一种最简单最基本的归并排序方法。
(2)算法的实现
二路归并排序算法是用分治法对 n 个元素进行排序的算法。其基本思想为：
将待排序的元素平分成大小大致相同的 2 个子序列，然后对每个子序列分
别使用递归的方法进行归并排序，直到子序列长度变为 1，最后利用合并算法
将得到的已经排好序的子序列合并成一个有序的序列。
二路归并算法的核心部分是归并操作，常用的方法是新建一个序列，序列
的大小等于要归并的两个子序列的长度之和。比较各子序列的第一个元素的值，
最小的一个就是排序后序列的第一个元素。取出该元素并放置到新序列的第一
个位置中，继续比较各子序列当前的第一个元素的值。如此反复，最终得到一
个有序序列。
归并算法将两个有序的数组段合并到一个新的数组段，然后又将新的数组
段再复制回原数组中。合并和复制的时间复杂度为 O(n)，归并算法的时间复杂
度为 O(nlogn)，是一个渐进最优算法。
3. 快速排序
(1)问题的描述
快速排序也称为划分交换排序，是由霍尔(Hoare)提出的一种冒泡排序算法的
改进版。在大多数情况下，它的时间复杂度为 O(nlogn)，故称其为快速排序。
(2)算法的实现
快速排序的基本思想是基于分治法的。
对于输入的子数组 a[p……r]，按如下 3 个步骤进行处理：
1) 分解：以 a[p]作为基准元素将输入的序列 a[p……r]分割成两个非空子序列
a[p……q-1] 和 a[q+1……r] ， 使 a[p……q-1] 中 任 一 元 素 的 值 都 小 于 等 于
a[q]，a[q+1……r]中任一元素的值都大于等于 a[q]。下标 q 在分隔过程中确
评论4