八十、归并排序及其分而治之思想

@Author：Runsen

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。 ---- Runsen

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

分治算法

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题
直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。（百度百科）

利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方法，例如二分法检索。

分治算法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

分治法所能解决的问题一般具有以下几个特征：

原问题于分解成的小问题具有相同的模式，原问题分解成的小问题可以独立求解，子问题之间没有相关性。

具有分解终止条件，当问题足够小时，可以之间求解，分解出的子问题的解可以合并为该问题的解

基本步骤

• 分解，将

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/111476672