分治法

到目前为止我们已经学过的两种排序算法，选择排序 和插入排序，最坏情况下运行时间为 $\mathrm{\Theta }(n^2)$‍。当输入数组的大小很大时，这些算法可能需要很长时间才能运行完毕。在本教程和下一篇教程中，我们将看到另外两种排序算法，合并排序和快速排序，其运行时间更好。 特别是，在所有情况下，合并排序在$\mathrm{\Theta }(n\lg n)$‍ 时间中运行，而快速排序在$\mathrm{\Theta }(n\lg n)$‍ 时间中以最佳情况和平均值运行，尽管最糟糕的运行时间是$\mathrm{\Theta }(n^2)$‍。下面是这四种排序算法及其运行时间的表格：

合并排序和快速排序都采用基于递归的通用算法范例。 这种范式，分治法，将问题分解为类似于原始问题的子问题，递归地解决子问题，最后将解决方案组合到子问题中以解决原始问题。因为分而治之是递归地解决子问题，每个子问题必须小于原始问题，并且必须有子问题的基本情况。您应该将分治法视为包含三个部分：

您可以轻松地记住分治算法的步骤，如 拆分，治理，合并。以下是如何查看一个步骤，假设每个拆分步骤创建两个子问题（虽然也有一些分治法算法创建两个以上）：

如果我们再扩展出两个递归步骤，就会看起来像这样：

因为分治法至少会产生两个子问题，分而治之的算法会产生多个递归调用。

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。