1.10.2.1.1. 常见算法学习

排序算法：十种
查找算法：七种
其他查找算法
- 树的数据结构和复杂度（时间和空间）
- 图：有向图、无向图、图的出度和入度
缓存淘汰算法：缓存算法（页面置换算法）-FIFO、LFU、LRU
排序算法：复杂度（时间、空间）

1.10.2.1.1.1. 排序算法：十种

十种常见排序算法可以分为两大类：

比较类排序：

1、冒泡排序（Bubble Sort）：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
2、选择排序（Selection Sort）：选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
3、插入排序（Insertion Sort）：插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
4、希尔排序（Shell Sort）：1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
5、归并排序（Merge Sort）：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
6、快速排序（Quick Sort）：快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
7、堆排序（Heap Sort）：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

非比较类排序：

8、计数排序（Counting Sort）：计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
9、桶排序（Bucket Sort）：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
10、基数排序（Radix Sort）：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

参考
十大经典排序算法（动图演示）
图解排序算法
 http://www.codeceo.com/article/10-sort-algorithm-interview.html#0-tsina-1-10490-397232819ff9a47a7b7e80a40613cfe1
面试中的 10 大排序算法总结

1.10.2.1.1.2. 查找算法：七种

查找算法分类

1）静态查找和动态查找；注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2）无序查找和有序查找。无序查找：被查找数列有序无序均可；有序查找：被查找数列必须为有序数列。

查找性能：从快到慢：顺序查找，时间复杂度O(N), 分块查找，时间复杂度O(logN+N/m); 二分查找，时间复杂度O(logN) Fibonacci查找，时间复杂度O(logN) 差值查找，时间复杂度O(log(logN)) 哈希查找，时间复杂度O(1)

[Data Structure & Algorithm] 七大查找算法

顺序查找
二分查找（折半查找）
插值查找
斐波那契查找
树表查找：二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，平衡查找树之2-3查找树（2-3 Tree）平衡查找树之红黑树（Red-Black Tree） B树和B+树（B Tree/B+ Tree）
分块查找
哈希查找：哈希表法（散列表）

顺序查找：条件：无序或有序队列。按顺序比较每个元素，直到找到关键字为止。时间复杂度：O(n)
二分查找（折半查找）：条件：有序数组先跟中间比较，再跟较大或较小那一边比较时间复杂度：O(logn)
插值查找
斐波那契查找
树表查找
分块查找：思想：顺序查找和二分查找的结合。原理：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。然后使用二分查找及顺序查找。时间复杂度：介于O(n) 和O(logn)之间。
哈希查找：哈希表法（散列表）条件：先创建哈希表（散列表）原理：根据键值方式(Key Value)进行查找，通过散列函数，定位数据元素。时间复杂度：几乎是O(1)，取决于产生冲突的多少。

参考 https://www.cnblogs.com/maybe2030/p/4715035.html https://blog.csdn.net/guoweimelon/article/details/50906299 https://zhuanlan.zhihu.com/p/37440434 http://codingxiaxw.cn/2017/01/14/66-leetcode-find/ https://juejin.im/post/5c7e843351882546c20a8669

1.10.2.1.1.3. 其他查找算法

参考 docs/SQL/数据库索引.md

查找算法：
1、最基本的查询算法当然是顺序查找（linear search），也就是对比每个元素的方法，不过这种算法在数据量很大时效率是极低的。
数据结构：有序或无序队列
复杂度：O(n)

2、二分查找（binary search）
数据结构：有序数组
复杂度：O(logn)

3、二叉排序树的特点是：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
搜索的原理：

若b是空树，则搜索失败，否则：
若x等于b的根节点的数据域之值，则查找成功；否则：
若x小于b的根节点的数据域之值，则搜索左子树；否则：
查找右子树。
数据结构：二叉排序树
时间复杂度： O(log2N)

4、哈希散列法(哈希表)
其原理是首先根据key值和哈希函数创建一个哈希表（散列表），燃耗根据键值，通过散列函数，定位数据元素位置。

数据结构：哈希表
时间复杂度：几乎是O(1)，取决于产生冲突的多少，也就是链表长度，因为链表查找复杂度为O(n)

5、分块查找
分块查找又称索引顺序查找，它是顺序查找的一种改进方法。其算法思想是将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，依次类推。

算法流程：
先选取各块中的最大关键字构成一个索引表；
查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

6、平衡多路搜索树B树（B-tree）
B树（Balance Tree）又叫做B- 树（其实B-是由B-tree翻译过来，所以B-树和B树是一个概念），它就是一种平衡多路查找树。

首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。
例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)

由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质

7、B+Tree
其实B-Tree有许多变种，其中最常见的是B+Tree，比如MySQL就普遍使用B+Tree实现其索引结构。

1.10.2.1.1.4. 树的数据结构和复杂度（时间和空间）

树的概念：
结点：指二叉树中一个个的点，就是下图中的0、1、2、3、4、5、6；
度：指父结点下面有几个孩子结点，举两个例子你就明白了。针对结点1，他下面有两个孩子3、4，所以说结点1的度为2；针对结点4，他下面一个孩子都没有，所以说结点4的度为0；叶子就是度为0的结点。
置于遍历有一点点麻烦，但要抓住以下要点就可以了（不管任何大小的树）：
前序：是先访问根，再访问左子树，然后访问右子树
后序：是先访问左子树，再访问右子树，然后访问根
中序：是先访问左子树，再访问根，然后访问右子树
完全二叉树，除了叶子结点这层外，其他层结点都是度为2的，所以这样的树高度应该最矮了。
以下图为例子：
前序序列：0134256后序序列：3415620中序序列：3140526

1.10.2.1.1.5. 图：有向图、无向图、图的出度和入度

图论（离散数学）：

出度和入度
可以把人与人之间为识的关系对应到一个图中。如果a认识b就a->b连一条边。
有向图来说，结常与结点间的连接。V1到V2，V1到V3。说明V1的出度是2。V2到V1说明V1的入度是1

数据结构中入度出度分别用什么符号表示
入度：ID in degree
出度：OD out degree

有向图顶点集的度数是不是等于出度加入度
在一个有向图中，所有顶点的入度之和等于所有顶点出度之和，一条边必有起点和终点，这是同时存在的，不存在一条边只有起点或者只有终点，所以所有顶点的入度之和等于所有顶点出度之和

在有向图中，入度高的点和出度高的点各自的含义是不同的。粗浅地说，出度高的点我们往往叫做Authority，就是那种权威性很好，所以对其他点影响力较强或者输出信息较多的点。而相应的，入度比较高的点称为Hub，即那种作为中介的，从别人那里获取信息比较多的点。当然，计算Authority和Hub更权威的方法有HITS算法等，往往并非单纯依赖出入度这么简单。

度数这个概念仅适用于无向图，即相邻的点的个数（或者说是连接的边的个数）。在有向图中，一般来说只分开考虑入度和出度，基本上见不到说把两者加起来记做度数的。

1.10.2.1.1.6. 缓存淘汰算法

缓存淘汰算法：缓存算法（页面置换算法）-FIFO、LFU、LRU

链表+HashMap实现LRU算法：链表存储数据项的顺序，HashMap存储数据项

FIFO：First In First Out，先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。双向链表：新来的数据放在链表尾部，淘汰时候删除头部

LRU：Least Recently Used，最近最少使用。链表+HashMap实现LRU算法：链表存储数据项的顺序，HashMap存储数据项

LFU：Least Frequently Used，最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。链表实现

LRU和LFU侧重点不同， LRU主要体现在对元素的使用时间上, 而LFU主要体现在对元素的使用频次上。

LFU的缺陷是：在短期的时间内，对某些缓存的访问频次很高，这些缓存会立刻晋升为热点数据，而保证不会淘汰，这样会驻留在系统内存里面。而实际上，这部分数据只是短暂的高频率访问，之后将会长期不访问,瞬时的高频访问将会造成这部分数据的引用频率加快，而一些新加入的缓存很容易被快速删除，因为它们的引用频率很低。

参考 /Users/yangzl/git/quickstart-cache/docs/缓存学习.md https://www.cnblogs.com/wyq178/p/11790015.html

1.10.2.1.1.7. 排序算法：复杂度（时间、空间）

这个简单。排序算法分为比较算法和非比较算法，其中比较算法包括交换排序「冒泡和快排」、选择排序「简单选择排序和堆排序」、插入排序「直接插入排序、希尔排序」、归并排序「二路归并和多路归并」，非比较排序有计数排序、桶排序、基数排序。「公式：不稳定的有：快些选堆」

1、冒泡排序。稳定的，平均时间复杂度为 O(n²)，最好时间复杂度那肯定就是一次循环 O(n)，最坏时间复杂度为 O(n²)。空间复杂度 O(1)。 2、快速排序。不稳定，平均时间复杂度为O(nlogn)，最好的时间复杂度为O(nlogn)，最坏就是选定的基准值在最边上，这样就是O(n²)，注意哦，快排的空间复杂度平均是 O(logn)，最差 O(n)。 3、简单选择排序。不稳定，平均、最好、最坏时间复杂度都为O(n²)。空间复杂度 O(1)。 4、堆排序。不稳定，平均、最好、最坏的时间复杂度为O(nlogn)。空间复杂度 O(1)。 5、直接插入排序。稳定。最好O(n)，平均、最坏时间复杂度O(n²)。空间复杂度 O(1)。 6、希尔排序。不稳定。最好O(n)，平均O(n1.3)，最坏肯定是O(n²)。空间复杂度O(1)。 7、归并排序。稳定。最好、最坏、最差时间复杂度O(nlogn)，空间复杂度O(n)。 8、计数排序。稳定，空间换时间。适合数比较集中在一起的，这样k就少了，时间复杂度为 O(n+k)，空间复杂度也为O(n+k)。「个人还是觉得其实空间复杂度为O(k)，因为我可以把值放回去的时候可以放到原数组上，所以是O(k)。」 9、桶排序，桶越多，时间复杂度很简单，为O(n+k)，空间复杂度最坏为O(n+k)，其中 n 是因为桶内部所有元素得排序， k 是指桶的数量。 10、基数排序，时间复杂度O(n*k)，k为最大数的位数，空间复杂度为O(n)。

堆排序的稳定性，如何实现堆排序，具体细节

我们知道堆的结构是节点i的孩子为2 i和2 i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。

堆排序。不稳定，平均、最好、最坏的时间复杂度为O(nlogn)。空间复杂度 O(1)。由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N logN)。

归并排序的稳定性，如何实现归并排序，具体细节

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。平均时间复杂度、最好情况、最坏情况均为O(nlogn)，辅助空间O(n)。归并排序。稳定。最好、最坏、最差时间复杂度O(nlogn)，空间复杂度O(n)。

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

说一下jdk自带的排序用到了哪些排序算法，展开讲一下 1、Arrays.sort() & Collections.sort() 2、JDK中的自带的排序算法实现原理精彩总结

jdk层面实现的sort总共是两类，一个是 Arrays.sort()， Collections.sort()；

1、Arrays.sort()

a、如果数组内元素是基本数据类型，最主要采用的是双轴快速排序「其实就是三路快排一模一样的思路，只不过三路快排中间是 = pivot1，而双轴快速排序是（pivot1，pivot2），具体戳链接：https://www.cnblogs.com/nullzx/p/5880191.html 。

总结就是数组长度小于47的时候是用直接插入算法，大于47并且小于286是采用双轴快速排序，大于286如果连续性好「也就是元素大多有序，有一个flag专门用来记录数组元素的升降次数，代表这个数组的连续性」采用的是归并排序，否则还是依旧采用双轴快速排序。

b、如果数组内元素是对象，采用的是TimSort.sort()，跟 Collections.sort()一样，都是采用的这个函数，这是归并排序算法和插入排序的结合。

Collections.sort()，采用 TimSort.sort()。

TimSort.sort() 大概原理： 1、当待排序元素小于32个时，采用二分插入排序，是插入排序的一种改进，可以减少插入排序比较的次数。当找到插入位置时，直接利用System.copy()函数即可。 2、当待排序元素大于等于32个时，进行归并排序（和传统的归并不一样），首先将排序元素分区，每个分区的大小区间为[16,32)，然后依次对每个分区进行排序（具体实现依然是二分插入排序），排完序的分区压入栈（准确的说不是栈，而是一个数组，用来记录排序好的分区），当栈内的分区数满足条件时，进行分区合并，合并为一个更大的分区，当栈中只剩一个分区时，排序完成。

经典排序算法----堆与堆排序（不稳定）经典排序算法----归并排序（稳定） https://blog.csdn.net/qianqin_2014/category_6339684.html

常见算法