常用数据结构总结
1、排序算法
https://www.cnblogs.com/Glory-D/p/7884525.html
注释：代码为伪代码
预备方法
//获取整形数组的最大值
def getMax(Array):
int max
for（int i：Array）
if i > max:
max = i
return max
//交换两个整形
def swap(a,b):
a,b = b,a
1、冒泡排序：
时间复杂度：O(N2),（时间复杂度的O的概念来源于数学中的等价无穷小）
思路：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
2、选择排序：
时间复杂度：O(N2)
思路：每次取出未排序序列最小（大）的放在未排序序列队首
def selectSort(Array){
for（i=0;i<Array.length;i++）:
minIndex = i；
for(j = i + 1;j<Array.length;j++):
if (array[j] < arr[minIndex]):
minIndex = j;
if(minIndex != i):
swap(i,minIndex)
}
3、快速排序：
时间复杂度：O(NlogN)
思路：每次找一个item作为分界点，将比item小的放在左侧，比item大的放在右侧，这种排序思路是一种树结构
https://www.runoob.com/w3cnote/quick-sort.html
为了完成上图的效果，代码实现上是这样做的，首先选择首位为基准key，首位在整个数据的左侧，那么我们就从右侧往前遍历，来回交替，如果是左侧小，右侧大，那么就是先将首位数字保存在key中，从右侧往前遍历，如果比key小就将当前位置与key的位置交换，接下来我们从前往后遍历，如果比key大就与Key的位置做交换。（思考一下，第一次交换位置后，按我们的搜索条件，key右侧的位置肯定都是比key大的，第二次交换位置后，key左侧的位置肯定都是比key小的，依次类推，逐步向中间逼近）（有没有一个疑问？为什么要从两侧而不是从一侧for循环一遍？想一下快速排序的过程,快速排序每次交换都保证了已经比较过的部分永远符合大的在key右侧，小的在key左侧，如果单侧for循环，你判断的依据只是一个条件比如比key小（或者大）在key左侧（或者右侧），并且你只使用一个指针，而两侧交替进行，使用两个指针，保证了两个条件同时的满足，这或许是我们要学习的地方，当我们需要满足两个条件时，我们应该使用两个指针）
通过上面的分析，所以完成算法需要三个要素，保存基准的key，记录左侧遍历位置的指针（这里是index），记录右侧遍历位置的指针。算法的实现流程如下图：
https://www.jianshu.com/p/4167ecfd23cb
3.1、随机快速排序
思路：在经典快速排序时，如果序列已经有序，则每次取首元素进行分治，产生的左右两个序列是不均横的，所以，可以通过每次随机一个下标，用下标对应的树作为分治点，这就是随机快速排序的思想。
3.2、二路快速排序
思路：随机快速排序虽然解决了数组基本有序的问题，却不能解决有大量重复数据的问题，如果有大量重复数据，随机快速排序时，仍然会出现分治极不均衡的情况，而二路快速排序解决了这个问题，我们在做经典快速排序时，是左边和右边依次交替遍历，二路快速排序的思想是左右两边同时进行，左边遇到你目标值大的就停下，右边遇到比目标值小的就停下，交换这两个位置的值，直到两个指针相遇。
3.3、三路快速排序
思路：之前的快速排序是将数组划分为 分成<=v和>v或者是<v和>=v的两个部分,而三路快排是将数组划分为分成三个部分:`<v、=v、>v，二路排序的优化，把等于value的元素放在另一个区间内，不参与下次的排序。
4、插入排序
时间复杂度：O(N2)
思路：数列前面部分看为有序，依次将后面的无序数列元素插入到前面的有序数列中，初始状态有序数列仅有一个元素，即首元素。在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
直接插入排序
https://www.jianshu.com/p/7cf0656e76dd
折半插入排序（插入排序搜索位置时使用折半查找）
https://www.cnblogs.com/liuzeyu12a/p/10492754.html
5、希尔排序
时间复杂度：通常认为是O(N3/2)
思路：希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
该方法因D.L.Shell于1959年提出而得名。
基本思想:先将整个待排记录序列分割成若干个子序列，分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行一次直接插入排序。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。【百度百科】
https://www.cnblogs.com/liuzeyu12a/p/10492754.html
6、归并排序
时间复杂度：O(NlogN)
思路：采用了分治和递归的思想，递归&分治-排序整个数列如同排序两个有序数列，依次执行这个过程直至排序末端的两个元素，再依次向上层输送排序好的两个子列进行排序直至整个数列有序（类比二叉树的思想，from down to up）。
归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如 设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
https://baike.baidu.com/item/归并排序/1639015?fr=aladdin
在算法实现上，归并排序的主要思想是递归和分治，我们拿到一组序列，首先从数组的中间分成两个数组，然后递归操作，最后再递归回来进行合并操作。
7、堆排序
时间复杂度：O(NlogN)
https://www.cnblogs.com/Java3y/p/8639937.html
思路：堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）；每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。
于是我们第一次的建堆操作就完成了！
可以发现的是：一次堆建立完之后，我们的最大值就在了堆的根节点上
随后将堆顶最大值和数组最后的元素进行替换，我们就完成了一趟排序了。
接下来，剩下的数不断进行建堆，交换就可以完成我们的堆排序了
.........建堆，交换....建堆，交换...建堆，交换...建堆，交换..
堆排序的代码实现利用了二叉树的一些性质，堆排序将数组看作是完全二叉树
完全二叉树有个特性：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2
完全二叉树(Complete Binary Tree)
完全二叉树编号及数组下标对应关系
https://www.cnblogs.com/Java3y/p/8639937.html
算法实现流程：
算法首先重要的是调整堆，即调整上图中虚线框中的三个元素，第一步，for循环从最后一个子树开始调整，将数组变成大根堆，然后取出根节点放在末尾，其余元素再次调整大根堆
8、桶排序
https://www.cnblogs.com/bqwzx/p/11029264.html
思路：桶排序思路是将序列中最大的树，铺开，变成多个桶，在序列中元素对应的桶中进行计数，最后从小到大或者从大到小输出桶中的数据，比如[1,4,4,6,1000]最大的元素是1000，我们生成1000个桶，第一、四、六、1000个桶分别命中，则在这些桶中进行命中次数的计数，其中1，6，1000桶中的计数为1，4号桶中的计数为2，则从有计数的桶中一次按计数次数输出值，则为1，4，4，6，1000
例子
代码实现
9、基数排序
https://baike.baidu.com/item/基数排序/7875498?fr=aladdin
思路：基数排序限制了桶排序的个数，限制桶为0到9。它根据排序元素各个位上的数字来进行分桶。
如序列：73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。
接下来将这些桶子中的数值重新串接起来。
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
我们发现此时序列已经变成个位有序序列。
接着再进行一次分配，这次是根据十位数来分配。
接下来将这些桶子中的数值重新串接起来。
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
十位数字也变成了有序序列
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
2、查找
1、二分查找
思路：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列
2、TOP-K问题
https://blog.csdn.net/laojiu_/article/details/54986553
https://www.e-learn.cn/content/qita/1224371
1、排序然后取出最大的K个。
2、局部排序，比如使用冒泡或者选择，每回都去取最大的值，则循环到K就可以了。
3、利用堆排序，前K个数建立小根堆，剩余的数依次与根比较，如果比根小，则新的数作为根，然后调整堆。迭代。
4、随机选择，利用快速排序加二分查找的思想，选择一个分治点，进行快速排序，如果右侧正好是k个数，则一次就找到了，如果右侧多于K则，再右侧继续分治，如果右侧小于k，则在左侧找剩余的m个数。
5、bitmap排序（桶排序）。利用计数，从大到小依次输出。
