算法系列： 10大常见排序算法: 分治的原理

一句

 分治法“分而治之”（Divide-and-Conquer），就是把一个复杂的问题分成两个或更多的相同或相似的子问题的策略

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是后面要介绍的几个高效排序算法的基础，所以今天就讲分治。

一个例子

问题：在全美国找到个子最高的那个人

美国有2亿多人，我们显然不会把2亿多人排一排，然后一个个比较。

常用策略是选出每个州的冠军。这就是“分”的过程

然后再总决赛，选出全美傻大个冠军。这就是“治”的过程。当然各个州比赛下面也可以再继续细分为各个县的比赛，各个县可以细分为各个学校的比赛。。。

为什么分治策略奏效？

先来看个例子：

聚会有10个人。如果每个人都和其他所有人打招呼，聚会一共有多少次招呼？

显然是9*10=90次。

聚会人多嘈杂，怎么办？把10人分到2个房间里，或者分为2组，一组5个人。 只有同组的人相互打招呼。那么每组中的5个人相互打了 4*5=20个招呼。2组一共打了20+20=40个招呼，相比10个人打90个招呼，清净太多了！

简单的结论

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，问题的复杂程度降低的越多，越容易直接求解。