分而治之 ：Divide and Conquer

1. 分而治之主要思想

2.分而治之在数组排序问题中的应用

2.1 插入排序

对于长度为Ｎ的数组A[0...N-1]进行排序，我们可以先对和原数组具有相同形式，但长度更小的数组A[0...N-2进行排序，然后把第A[N-1]数插入A[0...N-2中实现对原数组的排序。同样的为实现A[0...N-2]长度数组排序，我们可以先对长度更小的A[0...N-3]进行排序，最后将A[N-2]插入到已排序的A[0...N-3]中，实现对A[0…N-2]的排序。

如下图所示，我们求解N长的数组排序问题转化为求解N-1，N-2，N-3 ，，，1的数组排序问题，如前所述，涉及到了两个主要问题：

01  将N长数组排序问题转化为N-1数组排序问题
02  并把第N个元素插入到一个已经排好序的数组当中

插入排序伪代码

复杂度分析

不妨用$T\left(n\right)$表示对$n$ 长数组进行排序，$T\left(n\right)$有两部分组成，对前$n?1$的数进行排序，将第$n$个数插入到前$n?1$个数中,即：
$$\begin{gathered} T\left(n\right)=T\left(n?1\right)+O\left(n\right) \\ \le T\left(n?1\right)+cn \\ \le T\left(n?2\right)+c\left(n?1\right)+c\left(n\right) \\ \le T\left(1\right)+c\left(2+3+?+n\right)=O\left(n^2\right) \end{gathered}$$

2.2 二分归并排序

插入排序中由于子问题中数组元数为线性下降，每次减少一个元素，因此算法效率不高，为此我们引入归并二分排序，其主要思想是将A[0...N]数组排序问题转化为A[0....n/2]和A[n/2+1...n]数组排序问题，并将这两个子问题进行合并回到原问题，这里子问题大小是指数级下降，每次下降一半，提升计算速率。

伪代码

时间复杂度分析

同样的可以用$T\left(n\right)$表示二路归并排序的复杂度，它由二部分组成，对$A[0...N/2]$排序的时间复杂度$T\left(n/2\right)$及对A[N/2+1...N-1]的时间复杂度$T\left(n/2\right)$，以及子sorted 子数组合并的时间复杂度$O\left(n\right)$。
$$\begin{gathered} T\left(n\right)=2?T\left(\frac{n}{2}\right)+O\left(n\right) \\ \le 2?T\left(\frac{n}{2}\right)+cn=O\left(n\log n\right) \end{gathered}$$