数据结构中的分治算法解决问题-《数据结构与算法：Java版》

在数据结构中，很多问题是用分治算法的思路来解决的。

1.折半查找

在第7章中介绍的折半查找问题，在给定已按升序排好序的n个关键字a[0:(n-1)]中找出一特定元素x。下面分析一下折半查找问题是否满足用分治算法解决问题应该具有的4个特征。

（1）该问题的规模缩小到一定的程度就可以容易地解决；折半查找中如果序列中只有一个关键字，则直接通过比较就可以知道是否查找成功，查找完毕。

（2）该问题可以分解为若干个规模较小的相同问题；折半查找中，当规模减半后，问题仍是查找问题，是规模较小的相同问题。

（3）分解出的子问题的解可以合并为原问题的解；折半查找中子问题如果解决了，原问题也就解决了。

（4）分解出的各个子问题是相互独立的；折半查找中每次的子问题要么是前半部分，要么是后半部分，相互是独立的。

折半查找满足这4个特征，所以折半查找是适合用分治法解决问题的。那么按照分治算法的解题思路可以得到折半查找的查找思路为：要在n个关键字中寻找需要的关键字，先将待查关键字和中间关键字进行比较，比较中间元素后要么查找成功，要么将查找范围缩小至原来的一半，待查关键字比中间关键字小则到序列的前半部分继续查找，待查关键字比中间关键字大则到序列的后半部分继续查找。此时问题规模缩小了，但问题还是相同问题，还是要在n/2个关键字中寻找需要的关键字，所以仍用相同的方法来查找，直至找到需要的关键字则查找成功，或者最后序列中没有关键字则查找失败。这个过程就是将原来的大问题化成规模较小的小问题，当小问题解决了（找到或者找不到），原来的大问题也就解决了。

2.归并排序

在第8章中的归并排序问题，是要对n个无序记录的关键字序列进行排序的问题。下面分析一下归并排序问题是否满足用分治算法解决问题应该具有的4个特征。(www.xing528.com)

（1）问题规模缩小到一定程度容易求解；当只有一个关键字时，无序排序即有序序列。

（2） 问题规模缩小了仍然是相同问题；n个关键字排序和n/k个关键字排序均为排序问题，其中n为待排序关键字数量，k为分割的小问题数量，1＜k＜n。

（3）子问题的解可合并为原问题的解；子问题解决后，将小的有序序列合并（不同小序列中关键字依次比较，按大小将其存储在新的数组位置），可以得到大的有序序列，直到合并为一个有序序列。

（4）各个子问题互相独立。很明显，各个子问题（子序列）是相互独立的。

可以看出，该排序问题满足用分治法解题的4个特征，可以用分治法解决。那么按照分治算法的解题思路可以得到归并排序的排序思路为：将原n个关键字进行排序分解为两个n/2长度的子序列的排序，两个子序列排好序后再合并原序列就排好序了。如果两个n/2长度的子序列仍无法直接形成有序序列，则继续把序列划分成更小的n/4的小序列，直到序列中只有一个关键字，则序列已排好序。这也是一个将原来的大问题化成规模较小的小问题，当小问题解决了，经过合并后，原来的大问题也就解决了。

3.快速排序

第8章中的快速排序问题也是用分治算法解决的。前面分析了排序问题满足应用分治算法解决问题的4个特征，那么按照分治算法的解题思路也可以得到快速排序的思路为：先通过基准（枢轴）元素将原序列划分成两个小序列，分别再去解决这两个小序列的排序问题。两个小序列如果序列长度为1，则已排好序；否则继续用相同的快速排序方法对两个小序列进行排序。当两个小序列排好序后，整个序列也就排好序了，原来的大问题也就解决了。

这3个问题都是用分治法的思路来解决的问题，下面再介绍一些其他用分治算法解决的问题。