本文是几个markdown的合并，所以结构较乱，仅记录痕迹；
数据结构
双栈实现队列
《剑指Offer》09-用两个栈实现队列 – 分享技术成长历程～ – 博客园 (cnblogs.com)
散列表及冲突解决
散列表建立了关键字和存储地址之间的一种直接映射关系；从而加快查找速度；
散列表通常用于牺牲空间复杂度，来换取时间上的高效；
冲突：在散列函数散列关键字的过程中，可能会把多个不同的关键字映射到同一个地址；
减少冲突：好的散列函数可以减少冲突；
冲突是不可避免的，所以还要设计好 处理冲突的办法；
处理冲突：
- 开放定址法：空闲空间既向当前关键字的同义词开放，又向其非同义词开放；
- 线性探测法、平房探测法、再散裂法；
- 拉链法：把同义词用链表链接；
TOPN问题
海量数据中取最大的N个数：如，10亿个数中找出最大的10000个数；
首先要了解堆排序；
- 先拿10000个元素建堆；—O(n)
- 遍历剩下的所有，每次将一个元素加入堆，并调整堆，只保留前10000个元素（也就是每次插入后，最么一个元素不要，一直保持10000个元素堆）；—O(logn)
- 遍历完所有，剩下的就是要找的TOP 10000；—O(nlogn)
优化方式：
可以把所有10亿个数据分组存放，比如分别放在1000个文件中；这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。
图
排序算法
稳定性判别法：若存在不相邻元素间交换，则是不稳定的排序；
插入排序：直接插入排序
时间复杂度：
最好的情况下： 正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n) ；
最坏的情况下： 逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n2)；
平均情况下：O(n2);
空间复杂度：可能借用了”哨兵”，O(1)；
稳定性：直接插入排序是稳定的；（一个一个挨着来，不存在不相邻元素的交换，所以是稳定的；）
插入排序：希尔排序
希尔排序也是一种插入排序方法,实际上是一种 分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt
Original: https://www.cnblogs.com/kphang/p/16114498.html
Author: KpHang
Title: 408准备复试过程中整理的知识点（一）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/567386/
转载文章受原作者版权保护。转载请注明原作者出处！