数据结构和算法
树
平衡二叉树、B树、B+树、B*树 https://zhuanlan.zhihu.com/p/27700617
哈希
哈希表（Hash Table，也叫散列表），是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。哈希表的实现主要需要解决两个问题，哈希
哈希函数
哈希函数也叫散列函数，它对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构，同时散列结果应当具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值变化使得输出值发生巨大的变化）。
常见的冲突解决方法有开放定址法，链地址法，再哈希法、建立公共溢出区等。
数组和链表的区别
1、数组在内存上是连续区域，使用前需要先申请内存的大小（可能会浪费内存），而且不能动态扩展。插入和删除的时间复杂度为O(n)，支持随机访问，时间复杂度是O(1)。数组无需为表示节点间的逻辑关系而增加额外的存储空间，存储利用率高。
2、链表可以在内存上不要求连续，使用时不用指定大小，扩展方便。增加和删除数据的时间复杂度是O(1)， 查找访问的时间复杂度是O(n)
链表
单链表：只有一个指向下一节点的指针
循环单链表：尾结点指向头结点
循环双链表（双链表）：每个节点都有前驱和后继指针
静态链表：为数组的每个元素附加一个链接指针
链表有环问题和两链表相交问题
有环问题
1、是否有环：快慢指针
2、环的长度：从碰撞点到再次碰撞的长度
3、环的入口：碰撞点到入口的距离 = 头指针到入口的距离
相交问题
1、两无环单链表是否相交：人为构环，将A的尾结点指向B的头结点判断是否有环；直接判断两链表的最后一个节点是否相同
2、两单链表（不知是否有环）相交：
先判断是否有环：都无环回到1；一个有环一个无环必然不相交（画图可知）；两个都有环，快慢指针
堆（Heap）与栈（Stack）是开发人员必须面对的两个概念，在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层含义：
（1）程序内存布局场景下，堆与栈表示两种内存管理方式；
（2）数据结构场景下，堆与栈表示两种常用的数据结构。
递归和迭代
递归：程序重复调用自身，并明确有递归结束条件的编程称为递归。
使用要满足以下两个条件：
在过程或函数内调用自身；
必须有一个明确的递归结束条件；
迭代:利用变量的原值推算出变量的一个新值.
迭代：从已知推未知
递归：从未知回溯到已知，再推未知
循环和迭代的共同点在于，它们都是在描述一个多次操作
不同点在于，【循环】侧重于描述每次操作和上一次操作相同之处，而【迭代】侧重于描述每次操作和上一次操作的不同之处。
查找算法
顺序查找、二分查找、哈希查找、二叉树查找
1）插值查找算法：改变划分比例
2）斐波那契查找
排序算法
稳定性
稳定排序算***依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。
计算复杂度
依据串行（list）的大小（n），一般而言，好的表现是O(nlogn)，且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(nlogn)。
所有基于比较的排序的时间复杂度至少是 O(nlogn)。
常见的稳定排序算法有：
- 冒泡排序（Bubble Sort） — O(n²)
- 插入排序（Insertion Sort）— O(n²)
- 桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
- 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
- 合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
- 二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
- 基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间
常见的不稳定排序算法有：
- 选择排序（Selection Sort）— O(n²)
- 希尔排序（Shell Sort）— O(nlogn)
- 堆排序（Heapsort）— O(nlogn)
- 快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
选择排序：[3,3',2] 排序后 [2,3',3]
快速排序：[5，3，3，4，3'，8，7] 排序后[3',3,3,4,5,8,7]
希尔排序：一次插入排序是稳定的，多次插入排序不是稳定的。
快速排序
快排时间复杂度： 快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。 {50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。 由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。
最优：在最优情况下，Partition每次都划分得很均匀。 快速排序算法的时间复杂度为O(nlogn)
最坏：在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，最终其时间复杂度为O(n^2)。
平均： 快速排序算法的时间复杂度为O(nlogn)
空间复杂度：主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
希尔排序
是插入排序的改进，插入排序在小规模数据或者基本有序时十分高效。
希尔排序： 把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。对每个分组排序后，数组部分有序。
堆排序
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
十大排序算法
查看10道真题和解析
投递小米集团等公司10个岗位 >
看我名字。