复习（8）18章以前的内容

千山鸟飞绝，春风吹又生。

分而治之

简单来说就是对问题寻求分界，将分界之后的问题分别进行解决。

归并排序
注意第二点，对每一个子集合进行排序，实际上就是问题继续细分的地方
一种方法
第二种方法
第三种方法
平衡分割的方法
伪代码

简单来说，先将这个数组进行1.分割，随后对2.其中的每个元素进行排序，3.将排序好了的两个有序数组进行合并，4.如果无法分割，直接进行排序。
其中，2中的排序本身又是123的重复（分割成更小，排序，归并）

简单来说，当程序划分成两等分的时候，时间最小
排序的具体算法
归并排序实现
其实a和b都只是数组而已，只不过是被我们用某些参数分了阶段，递归的过程，可以用不断地将两个小部分合成为二倍地长度并且重新储存来概括，也就是图片中的这样。
精华是第四部分
简单来说就是一个归并的过程，只不过是在同一个数组中进行（其实在不在是没有影响的）
第一部分的比较，是将较小者的数据进行储存，并且较小者和指针的浮标一起进行移动
第二部分，就是将剩余部分进行整体的移动，因为已经排过序所以不用考虑顺序的问题。
这里递归有一个作用就是，在递归进行的过程中，实际上当函数返回开始排序的时候，数组中的元素已经不是调用排序的时候的样子，而是改变了，但是定位是不会变的，始终都是精确的关系。
具体的使用和实现
这里要注意的是，倒数第二个的地方条件实际上是反了，如果是小于n的话，才是应该直接传递，否则不可能继续进行递归。
快速排序
具体实现
前半部分比较重要

精髓在于，首先找到左边第一个大于的，然后是右边第一个小于的，然后进行交换，如果顺序倒位就返回。

总结
改进
比较
选择问题
改进
其实选择问题追求的不是有序，只是一个数而已
将对应的数组进行初始化
具体过程
关键是最后一句，如果当前的点正好就是那个数字的话就可以返回了
改进
如果大于就到左边找k大，如果小于就到右边减去当前值找k1大
所谓的拥有更好的平均性能，就是这种方法不一定是排序完整个中间过程，但是如果是先排序后查找，那肯定是不行的，所以是<nlogn的水平
最优化问题
从17章开始实际上讨论的都是最优化问题，解决这个问题可以通过贪婪算法，也可以通过动态规划，而对于可以明确指出优化函数（换句话说，就是达成目的有明确的方法）的问题，一般采取贪婪算法
贪婪算法的关键就是这个，也就是当前的决策不能受到之后的干扰，所有的子最优决策结合起来就是总的最优决策
无论是贪婪算法还是动态规划，都是需要将每一步的选择变成一个统一性的问题解决，这个问题就可以简化成若干步从接下来的箱子中找一个适合的箱子的问题，对于贪婪算法来说，这个选择的原则就是：选择最小的（不受后面影响）
所谓的拓扑排序……就是考虑到前后逻辑关系的基础上，选出能够合理达到的序号顺序
简单来说就是一个原则——我们最终选出的答案是一个序列的形式，也就是一个数组，所有的边的前后点，在序列中的顺序必定也是前后排列的
也就是，每次取出的点，必定是能够从已有的点中导出来的
感觉这里有点儿问题，应该是选取存在边，因为并不是所有的前点都存在于数组中的时候才能够导入下一个点，但是这个算法并不是为了仅仅保证能够选出来，之后的证明可以给出
如果失败了，就说明到了最后一定有一个边没选进去，那么必然又存在另外一个点不在里面，那么又有下一个不在里面，这一个若是重复，就是环结构，必然不可行，如果不是继续推断，最后总有一个环路
所以问题的解决方法就变成，从一开始选择一个入度为0的顶点加进去，然后根据其所导引的所有点，将每个点的入度（这里的入度的意思实际上变成了引向它的顶点还没被加进去的个数，然后将所有已经变成0的点加进去，然后继续此过程）
具体过程
所谓的拓扑排序其实不是排序啊，也就是将一群数组从一个固定的规则中选择出一个随即顺序而已，此外，这也不是图论相关，仅仅是在数组中对于数组操作而已
过程1
theorder为实际答案的数组和序列
这里的重要步骤，用设定好了的迭代器对此顶点进行迭代，只要取出来的下一个顶点的数字，就将其indegree减一，然后如果已经为0，就压进去
image.png
迪杰斯特拉算法，重点了

综述一下，就是首先从出发点选出所有的边，然后将最小的选进去，然后在当前这个最小边的基础上，看看其所能到达的边，如果这些边不存在就进行更新，如果存在就比较，代价小的情况下再进行更新，然后继续选当前代价最小的边，存入，继续循环

第二条的扩充，就是由这个点再进行接下来的遍历
image.png
image.png
image.png
主要就三个数组，一个用来记录对应点的距离，一个用来记录对应点的前一个点，一个用来记录当前所有可以选择的点，所以基本上都是按照点来对应数组中的元素的，没有什么绕
image.png
精髓的操作，一个是将邻接的点的前置点进行更新，一个是将其对应的最短距离进行更新，最后，将这个点进行候选的储存
image.png
image.png
总的复杂度是n2级别
克鲁斯卡尔算法
image.png
image.png
这里的重点就是是否会产生环边的问题，环边，其实也就是——在这个边被选定的时候，实际上这个点已经存在于这个图中了，只是没有这条边，换句话说，从已知的图到此点是有一个路径的，只是不是你当前选定的这个路径甚至可能不是单条路径，但是你又找出一条，这就是环路，也就是说，对于我们新找出来的一条边来说，首先考察，如果两个点已经处在同一个子图，那么就不行，如果不是，那么就可以连接，并且连接之后两者变成一个子图。
这使用并查集来实现
此外，由于每次要进行的是最小边的选取，所以是选择小根堆来进行数组的初始化比较好
image.png
image.png
image.png
image.png
image.png
普利姆算法
image.png
终于复习完一章了，感觉并没学到什么东西，有点儿要命
都说按部就班是最好的努力方法，其实最好的努力方法应该是按部就班外加偶尔拼命，可惜，年轻人，你的路走窄了
不过没关系，继续吧，接下来是图论知识。
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
15章
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png