408
数据结构 7 查找
B树
所有节点平衡因子均为0的多路平衡查找树
所有节点都在同一层
至少有m/2向上取整个子树
插入 从底部向上插入，如有必要进行分裂
分裂 中间数值向上，两边分裂
删除 不在终端，找前驱后继；终端，足够直接删除，不够找兄弟借，其次合并兄弟和上方
B+树
关键字代表子树最大值的B树变形
叶节点包含全部关键字，非叶节点仅索引
叶节点穿成一线性链表
散列表Hash
通过散列函数确定
冲突-函数分配，聚集-处理冲突不当
构建方法：直接定值 - ax+b线性函数；除留余数 - x%a；数字分析 - 其中几位比较均匀；平方取中 - 不够均匀
处理冲突-拉链法：同一位置的用链表相连
处理冲突-开放定值：线性探测 - 直接123；平方探测 - 数平方加符号，4k+3的素数；双散列法 - 乘第二个表；伪随机 - 直接给出
查找效率：散列函数，处理冲突方式和装填因子。装填因子为记录数/长度
数据结构 8 排序
稳定性指同数值的两个数在排序中是否改变位置
插入排序
前方一部分有序
直接插入
稳定，n2，适用链式和顺序
折半插入排序：插入时折半，只适用于顺序
希尔排序
缩小增量排序，按子表顺序缩小间隔，不稳定，只适用于顺序，时间复杂度未知
交换排序
将一个值交换到正确位置
冒泡排序
稳定，n2，适用链式和顺序
快速排序
分治法，选择一个数，将左右分为大小区域，不稳定，适用顺序
时空效率：空间，使用递归，从log n到n；时间效率n2，实践最好
选择排序
选择正确的顺序插入
简单选择排序
遍历选择再插入，不稳定，适用链式和顺序，始终n2
堆排序
构建堆并拿走根节点
堆：构建从下往上，删除后，将最后值提上，再向下调整
构建时间n，堆排序时间n log n，不稳定，适用顺序
归并排序
不断归并相邻组，时间n log n，空间n，稳定，适用链式和顺序
基数排序
对各位数字进行比较，稳定，适用链式和顺序，时间d(n+r)，d是次数，n数量，r类别
计数排序
累积出现次数，根据出现次数判断顺序，稳定，时间n+k，k辅助队列长度，适用顺序
内部排序比较
时间，空间，稳定性，适用性，过程特征综合考虑
数据数量，初始状态，关键字结构和分布，稳定性要求，存储结构和辅助空间考虑
外部排序
要和外存沟通的排序
基本法
归并处理，输入区+输出区，
先得到初始归并段，再归并
时间：内部排序时间 + IO + 归并时间
提高：初始归并段减少或增加归并路数
败者树
减少归并次数，完全二叉树，存储失败数，新数直接比较自己的路径叶子到根，log n
并非越大越好，会减少每路长度
置换选择排序
保存已经输出的最大值，将大于最大值的输入的不断输出，直到全部小于
最佳归并树
让记录少的先归并，哈夫曼树，IO=WPL*2
不满足严格K叉数(度为0或K)，加入0的段，k度的节点(n-1)/(k-1)