谈谈数据结构与算法【四】
常用数据结构与算法清单：
数据结构：数组、栈、队列、链表、二分搜索树、集合、映射、堆、线段树、前缀树、并查集、平衡二叉树、2-3树、红黑树*、哈希表、图。*
算法：选择排序、插入排序、冒泡排序、希尔排序、归并排序、快速排序（双路、三路）、堆排序、二分查找法、Prim算法、Prim算法、Dijkstra单源最短路径算法、Bellman-Ford算法。
温馨提示：本文不对数据结构的底层具体实现以及在Java中的具体多种容器实现进行解析。
上次我们讲完了常用的数据结构，接着我们来将将常用算法,本文图片均来自网络，若照成侵权，请及时联系作者进行删除。
递归
递归本质就是将问题转化为更小的同一问题，递归函数就是一个函数，完成一个功能。
一句话理解递归：
古之欲明明德于天下者，先治其国；欲治其国者，先齐其家；欲齐其家者，先修其身；欲修其身者，先正其心；欲正其心者，先诚其意；欲诚其意者，先致其知，致知在格物。物格而后知至，知至而后意诚，意诚而后心正，心正而后身修，身修而后家齐，家齐而后国治，国治而后天下平。
只可意会！！！
递归的代价：函数调用+系统栈空间
选择排序 O(n^2）
编码简单，易于实现，是一些简单情景的首选，在一些特殊情况下，简单的排序算法更有效，简单的排序算法思想衍生出复杂的排序算法，可以作为子过程，改进更复杂的排序算法。
思路：从小到大，找出最小的元素放到第一个位置，再从剩下的元素中找到最小的元素，放入当前剩下空间的第一个位置。
插入排序 O(n^2）
思想：从小到大，假设对一个数组的元素进行排序，首先第一个元素不用动，然后后面的元素与之前的元素进行比较，每比较一个元素，如果比前面的元素小，就互换位置，接着再和前面的元素依次进行比较。
插入排序法的改进 （有序前提下为O(n)）
插入排序在遍历的过程之中也是在交换的过程。所以性能比O(n^2)的选择排序还要差。
改进思路：
1.数组的第一个元素为8，第二个元素为6，从6位置开始进行遍历，此时的6比8要小，先将6复制一个副本出来：
2.接着判断6这个元素是否应该放在原先的位置上，怎么判断呢？就是与前面的那个元素进行比较，如果比它小，说明6不应该放在此时的位置上，而8应该放在当前的位置上。所以8向后移动一个位置，接着再判断6是否能放在前面一个位置，因为前面一个位置为第一个位置，所以就不需要再进行比较，直接将6放入该位置即可，依次类推的比较后面的元素。
此时的优化是：一次比较一次赋值操作。
当内容是完全有序的话，插入排序的性能是O(n)的。
冒泡排序 O(n)
思想：例如从小到大
比较相邻的两个元素，值大得交换至右边。每一趟Bubble Sort都将最大的元素放在了最后的位置。
希尔排序 O(n^2)
思想：例如从小到大，当前元素与前面所有元素进行比较赋值操作，比前面的元素最小的元素进行位置互换。
归并排序 O(nlogn)
思路：首先将数组中元素归成左右一半，再把左边的元素进行排序，再把右边的元素进行排序，接着进行合并，再对左边的元素归成左右一半，再对右边的元素归成一半，再对它们进行排序，再合并，依次类推，直到每个部分只有一个元素。
归并的次数与元素个数N的关系：log(N)。时间复杂度：O(nlogn)。
利用临时空间进行排序，再进行归并操作。不过存储操作为O(n)。
分析例子：8 6 2 3 1 5 7 41.首先进行分组操作，从中间的位置开始分。
8 6 2 3 | 1 5 7 4
2.接着对两边进行排序：
2 3 6 8 | 1 4 5 7
3.利用临时存放空间，将排序好的元素放进去。接着对当前的空间与临时空间的元素进行索引下标追踪:
上边的下标表示最终归并的过程中需要追踪的位置，下边的两个下标分别指向两边排序好的数组当前要考虑的元素。
4.此时对下边的两个下标元素，进行判断，判断哪个谁应该先放入上边下标追踪的位置上，由于此时1比2小，所以1先放进去，接着上边的箭头就移到下一个位置，1所在的数组的下标也要移动到下一个位置上：
5.接着考虑2和4，判断谁先进去上边追踪的位置里。依次类推。
当数组是有序的话，归并排序的性能要比插入排序要差,当数组的元素比较少时，使用插入排序。
自底向上的归并排序算法前面所分析的为自底向下的归并排序，也可以进行自底向上的归并排序。
思路：自底向上的归并排序：以数组为例，直接将数组分成若干个组，例如每个组两个元素，然后对每个组进行排序，接着就是向上归并操作，接着在分成每段四个元素进行排序，再进行归并操作，以此类推。该操作不需要借助递归，只需要利用迭代就能完成。
另一种优化：一次性申请aux空间, 并将这个辅助空间以参数形式传递给完成归并排序的各个子函数。
快速排序 O(nlogn)
以数组为例，从大到小排序。
分析例子：
思想：
1.先找到第一个元素为基点，此时第一个元素为4，将它放入此元素排序好的位置去：
2.接着将小于4的部分与大于4的部分，依旧进行快速排序。
如何将4这个元素移到正确的位置上呢？进一步分析：
我们对这一过程称为子过程（Partition）：
j：分界点。
i：当前访问的元素
当元素e>v的话，直接放在>v这一部分，然后就可以去判断i++的元素。
如果元素e<v的话，我们只需要将j后一个位置的元素与i所指的元素进行交换：
此时就需要对j进行++。
接着再进行i++，对下一个元素进行考察即可，以此类推:
当数组遍历完成后：数组就变为三个部分，v v
遍历完成后，就可以对l和j这两个位置的元素进行交换。
不过此时完成的快速排序，在有序的数组归并排序很快就能完成排序，而此时的快速排序却非常的慢。
归并排序：每次都将数组一分为二，接着再对子数组一分为二，以此类推。
整个层次是logn层的，所以性能为O(nlogn)。
快速排序：归并排序能保证每个数组都是平均的一分为二，对于快速排序则没有这个保证。
由于分成的两个部分可能不是平均的，所以不能保证其高度为logn，最差的情况为n2,所以最差的性能为O(n2)。
当数组完全有序的时候，就没有分出左边的数组，所以此时的高度就为n。由于高度为n,又每次操作为O(n),所有性能为O(n^2)。
解决这个问题有如下的方法：随机化快速排序法、 双路快速排序法、三路快速排序法。
随机化快速排序 O(nlogn)
由于当数组有序时，也就是快速排序法的最差情况下，每次选定的都是最左边的元素，而我们又希望能选择整个数组中间的位置元素，如果不能准确的定位中间位置的元素，我们可以利用随机选择一个元素，此时的利用随机选取的快速排序的期望值为nlogn。
此时的快速排序的最坏情况还是为O(n^2),不过这一情况的概率几乎为0。
我们需要看元素e是大于V还是小于V，然后将元素e放入不同的位置，这样将数组分成两个部分，递归下去进行快速排序。
如果e等于V呢？
之前我们代码中对大于V的的操作不需要改动，只需要考虑小于V的情况，对e进行放入，而当e等于V，就相当于被我们前面的大于V情况中考虑进去了。
可以可以改变代码变成：
由于重复的元素太多，所有此时的数组就可能变为极度不平衡的两个部分：
或者：
此时的快速排序就会退化成O（n^2）。
解决这种情况就要利用双路快速排序法。
双路快速排序
之前的随机快速排序法都是大于V小于V都放在了数组的一头，然后i从左到右的遍历完成整个数组。
改进：
将数组的大于V和小于V放在数组的两端，此时就需要新的索引 j。
j：大于V这一端下一个需要扫描的元素的位置。
分析：
1.首先从位置i开始向后扫描，当我们面对的元素仍然是小于V的时候，就继续向后扫描，直到碰到某一个元素e大于V，此时就停止。
2.同样对于j,从j向前扫描如果元素大于V就继续向前扫描，直到碰到某一个元素e小于V，此时就停止。
此时蓝色部分就要归并到橙色和紫色部分里去：
再对i和j两个位置的元素e进行交换位置即可：
随后i索引接着向后查看i相应的元素，j索引接着向前查看j相应的元素。
直到i和j重合，就代表整个数组遍历完毕。
其实图中描述的是大于等于V和小于等于V的方式：
此时的等于就被分到了左右两部分中去了。
当i和j两个元素相等时，也要进行交换位置，这样就不会出现重复的元素聚集在一边的情况了。
三路快速排序
思想：
三路快速排序是将数组分成3个部分，小于V，等于V，大于V。
在递归的过程中等于V的部分就不需要进行管理，只需要对小于V和大于V进行管理。
lt表示小于V的最后一个元素。
gt表示处理后的大于V的第一个元素。
对i元素的情况进行讨论：
1.e == v：e就纳入等于v的部分中，然后i ++。
2.e < v：和等于v的第一个元素进行位置交换，接着维护lt，lt ++，然后i ++，去查看下一个元素e。
3.e > v: 和gt-1这个元素进行位置交换，接着gt --，此时的i不需要维护。
当数组出来完成之后为这样：区间为前闭后闭。
当处理完成之后，就对小于V和大于V的部分进行递归的快速排序即可，而等于V的部分已经放入合适的位置中了。
此时的快速排序性能要比归并排序性能要好。
堆排序（O（nlogn））
对数组从小到大进行排序，利用堆，将数组存放进堆中，接着从n-1位置开始对堆中的元素进行遍历打印。
原地堆排序：
堆的第一个元素就是值最大的元素：
1.由于我们的排序是从小到大，所以这个最大的元素应该放到数组末尾的位置，所以v和w要进行位置交换。
此时的堆已经不是最大堆了，因为w这个位置的元素不再是最大的元素：
2.此时要变为最大堆就要对w进行Shift Down操作，此时最大值的元素又再第一个位置了：
3.第二次交换：依次类推，从第一次操作之后，每次都对Shift Down操作后的新的最大堆中的第一个元素v和新的最大堆（红色部分）的最后元素w进行交换位置，再对交换完成后的w元素的这个位置进行Shift Down操作，依次类推。
直到整个数组都是蓝色的，就代表数组从小到达排序完成。
由于数组是从0开始索引的，所以堆也要做相应的调整：
parent(i) = (i - 1) / 2
left child(i) = 2 * i + 1
right child(i) = 2 * i + 2
最后一个非叶子节点的索引：(count - 1) / 2
将n个元素逐渐插入到一个空堆中，算法复杂度为O(nlogn)。
Heapify过程为O(n)。
二分查找法
对于有序数列，才能使用二分查找法（排序的作用）。时间复杂度：O(logn)
以数组从小到大进行排序为例。
思想：找到有序数组中间位置的元素，和我们要查找的元素进行比较，如果要找的元素大于数组中间的元素就去右边寻找，如果小于就去左边寻找，以右边为例，再对右边的中间位置进行比较，依次类推。
由于图算法在实际终很少有用到，所以这里就不做介绍了，有兴趣可以阅读我笔记博客做的总结。