由归并排序和快速排序引申的思考

分治算法

归并排序和快速排序都使用了分支算法的思想。

分治算法：顾名思义，就是将原问题分割为同等结构的子问题，之后将子问题逐一解决后，在解决了各个小问题之后(各个击破之后)合并小问题的解，从而得到整个问题的解。

归并排序：分的时候没有过多考虑，直接简单的一分为二，然后不断递归就可以了，但是在合的时候，就需要考虑怎么合在一起了。

快速排序：费了较大的功夫去考虑怎么分为两部分的问题，我们写了partition这个方法来进行分割，在这个基础上，合在一起就比较简单了，只需要不断递归就可以了。

分治算法基本思想及策略

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

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

可使用分治法求解的一些经典问题

• （1）二分搜索
• （2）大整数乘法
• （3）Strassen矩阵乘法
• （4）棋盘覆盖
• （5）合并排序
• （6）快速排序
• （7）线性时间选择
• （8）最接近点对问题
• （9）循环赛日程表
• （10）汉诺塔

分治算法相关博客介绍：https://www.cnblogs.com/xsyfl/p/6921687.html

五大算法思想

• 1、分治算法（代表：归并排序、快速排序）
• 2、动态规划算法
• 3、贪心算法
• 4、回溯法
• 5、分支限界法

关于这五点，这里先列出来，后续再进行总结。

问题1：求解数组中的顺序对、逆序对

顺序对：在一个数字集合中，如果存在前面的数小于后面的的数字，那么这就称为顺序对，反之，则是逆序对。

下面，我们将尝试统计一组数据中顺序对逆序对的个数。

1、暴力解法

暴力解法：用两个循环，依次寻找顺序对、逆序对，时间复杂度：O(n^2)

2、使用归并排序

上图是我们前面将归并排序的博客用的图片，我们看最后两行，在归并排序的 归并过程中，我们会比较左右两部分数据的大小，首先比较 10 和 50 的大小，10比50小，所以10比右边的50后面的所有数据都要小，此时，就可以用一个计数的变量来记录，有四个顺序对。同理可以记录逆序对。

这个算法过程和归并排序的过程是一样的，只不过增加了顺序对和逆序对的计数器.

问题2：得到数组中的最大值、最小值、第n大的元素

1、得到最大值最小值比较简单，遍历一遍就可以了，时间复杂度O(n)

2、得到第n大的元素

• 1、对整个数组排序，可以前面提到的快速或者归并排序，先排序，然后取对应角标的值即可，时间复杂度O(NlogN)
• 2、可以利用快速排序的思路，在快排中，每次排序完成都会有一个锚点v，如果v刚好等于n，则就找到了第n大的元素，如果n > v, 则我们只需要继续在n>v这一部分去排序排序即可，如果n<v,就只需要对小于v这一部分数据继续使用快速排序。这样，就比方法1更快一些，当然时间复杂度依然是O(NlogN)

具体代码可以参考前面两篇博客对 归并排序和快速排序的代码实现。