第3章 分而治之算法

我们来学习一种新的算法策略——分而治之，顾名思义，先“分”而后“治”，“分”就是将整体划分成部分，“治”就是先求解部分问题，每个部分问题都解决了，整体也就解决了，“天下难事，必作于易；天下大事，必作于细”。生活中有很多使用分而治之方法的例子，比如，夏天比较热的时候，我们最喜欢买一个大西瓜解渴，但是西瓜太大不好入口，通常我们会将西瓜切成一块块来吃，这就是拆分；再比如我们平常看到的汽车，汽车的工艺很复杂，但是也是由不同的零件组成的：发动机、车轮、玻璃、方向盘等，我们只要将每个零件生产出来，然后组合在一起，就是一辆可以跑的汽车；又如公司的组织结构，首先是CEO，CEO下面是各个总裁，总裁下面是各个经理……，层层分下去，才可以让一个公司有条不紊地运行下去。可以这样说，只要事物到达了一定的规模，就需要不断地拆分，然后求解。

本章主要涉及的知识点如下：

● 纵横捭阖，各个击破——分而治之：学会分而治之思想的本质及分而治之算法的核心要素。

● 真币or假币——伪币问题：通过伪币问题，学会使用分而治之算法进行假币判断。

● 再谈排序算法（1）——合并排序：在第1章我们已经学习过冒泡排序、简单选择排序、直接插入排序，在此学习使用分而治之思想进行数组排序。

● 再谈排序算法（2）——快速排序：使用分而治之思想进行数组排序的另一种算法。

● 累人的比赛——循环赛日程安排：结合实际生活中的比赛问题，学会使用分而治之算法进行循环赛日程安排。