7.高级排序：
希尔排序：实现简单 不快不慢 稳定
插入排序：复制的次数太多 极端情况下表现不好
n-增量排序 ：逐渐减小增量 计算间隔的公式h=3*h+1 Knuth
0 1 2 3 4 5 6 7 8 9 10 11 12
第一小的肯定在第一组
第二小的肯定在第二组、第一组
h=4,8
h=4
outer=4
temp = array[4]
innner=4
0和4进行比较
0 和 4交换位置
outer =5
temp = array[5]
inner =5
4和0
5和1
6和2
7和3
8和4
9和5
算法不会重复比较吗？
逐渐减小间隔，最后一定等于1 最后一趟排序是一次普通的插入排序
划分：枢纽
保证比枢纽值小的在左边、比枢纽值大的在右边
极端：所有数据都比枢纽值小或者大，徒劳操作
划分的效率：O（N）
快速排序：
枢纽的选择：具体的数据项 任意数据项
实质：找到枢纽的最终目的 交换一次位置
理想：应该选择数据项的中值 最坏的情况O（N2）
选择合适的枢纽成为关键：全部数据计算no 随机计算no 三数据项取中
处理小划分：对于小划分使用插入排序
消除递归：现在的系统可以更为有效的处理方法的调用
基数排序：不需要比较的排序 利用计算机高速位运算
第一趟子排序 第二趟排序 。。。。
基数排序的效率：
8.二叉树：有序数组（查询快,腾空间费时）、链表（插入快）
有序链表
常用的术语：路径、根（根到任意节点的路径有且只有一条）、父节点、子节点、叶节点、子树、访问（执行某种操作）、遍历、层、关键字、
树解决问题：边（引用） 节点（对象）。多路树 ---->特例、二叉树
二叉树：一个节点的左子节点的关键值小、右子节点大
一个类比：分级文件结构
二叉搜索树工作：
非平衡树：缺少左、右子节点，插入顺序是升序或者降序时将出现非平衡树
节点类概念，数据项抽象出来
Tree类：根节点
节点类：数据项、左子节点、右子节点
增删改查
树大查询效率：log2N，查找节点的时间取决于节点所在的层数
树的插入：
遍历：前序、中序、后序 递归遍历 前缀表达式、后缀表达式
查找最大值最小值：最左边的节点最小值、最右边的节点最大值
树结构的本质规律：每棵树最左边节点为最小值，最右边节点为最大值，只要满足这个要求即可
删除节点：1.删除叶节点，从树中移除即可、
2.删除包含一个子节点的节点，改变父节点的引用指向子节点
3.删除有两个子节点的节点 平衡被打破了。 需要填补上。 太聪明了
二叉树效率：大O表示法，log2N 一颗满树大部分节点都在底层
使用数组表示树：位置 2*index+1 不允许删除的操作
重复关键字的问题
压缩、解压原理：
哈夫曼编码：原理减少表示最常用字符的位数量 每个代码都不能是其他代码的前缀
频率表 出现次数最多的字符所占位数应该最少
创建哈夫曼树解码：
创建哈夫曼编码
9.红黑树：遵守一定规则的插入，目的保持平衡
二叉树的问题：有序插入表现不太好 存在不平衡树 插入效率lon2N到N
平衡的补救：红黑树 特征：节点都有颜色
红黑规则：每个节点不是红色就是黑色
根总是黑色
如果节点是红色的，则子节点必须黑色
从根到叶节点的每条路径，必须包含相同数目的黑色节点，即黑色高度必须相同
重复关键字的平衡：
修正违规的情况：改变节点的颜色 执行旋转操作
非平衡树
总之达到的目的树相对平衡，过程相当繁琐
其他平衡树：AVL树左子树和右子树高度差不能超出1
10.2-3-4树和外部存储
每个节点最多有4个节点、3个数据项 所有叶节点总是在同一层
非叶节点存在的情况：子节点的个数比节点的数据项个数多一
空节点不会存在的
child1子树的所有子节点的关键字小于key0并且大于key1
child2的子树所有子节点的关键字值大于key1并且小于key2
搜索2-3-4树：
插入：
节点分裂：向下寻找插入位置时，节点已经满了，为了保持平衡，就必须分裂
将数据向上和向右移动
在下行路中分裂：任何分裂节点的父节点肯定不是满的
什么时候分裂：满了就分裂
2-3-4树可以转变为红黑树：旋转和变色 等价于 分裂
存储需求：只是利用了5/7的可用空间 红-黑树在存储上比2-3-4树利用更高
2-3树：节点分裂：2-3-4数载所有分裂完成之后才会插入新数据，2-3树中新的数据项必须参加分裂过程
分裂的目的还是保持平衡
外部存储：数据存储在RAM，磁盘存储
快速查找、插入、和删除
主存：一秒的百万分之一访问一个字节
磁盘：1秒的千分之一 10毫秒 读写头移到正确磁道、读写头旋转到正确的位置 每分钟10000圈，
数据按照数据块来存储 一次访问一个数据块
顺序有序排列：按照某个关键字为所有记录排序
查找：2分查找
插入：移动太频繁 数据块的频繁读取和写入操作 关键字的问题
B-树：多叉树 纪念我们的伟人R.Bayer和E.M.McCreight外部存储的数据结构
每节点一个数据块 在磁盘中链接是文件中的块的编号int型
17阶B树
B树的效率：读取的效率log9N 删除、插入5+6<500000
索引：关键字---数据块组成列表 索引比文件实际记录小的多，完全可以放在内存
查找：
插入：插入
多级索引
对内存来说索引太大：在磁盘中存储成B树结构 数据项保存关键字和指向主文件中的一个块指针
组合搜索条件：顺序查找
外部文件排序：块内部有序 读取两块合为一块有序 归并排序
11.哈希表
哈希表的速度快于树
缺点：基于数组、难于扩展、哈希表被基本填满时，性能下降的非常严重
哈希化：关键字直接用于数组下标、哈希函数
关键字作为索引、数组
字典：字典、编译器（哈希表保存符号表、符号表）
单词和数组下标建立联系 数字相加
50000个单词 没办法把单词分的足够开 27的幂 产生的数组下标太多
哈希化：取余数。
哈希函数：把一个大范围的数字哈希转化成小范围的数字
取中：每两个数组单元、就有个单词、这些单元没有单词
冲突：没有太多的单词有同样的数组下标
解决冲突的方案：开放地址法 通过增加空位、减少冲突 链地址法：
开发地址法：寻找空白单元（线性探测、二次探测、再哈希法）
线性探测：聚集、导致较长的探测长度，意味着存取序列最后的单元非常耗时。装填因子：已填入哈希表的数据项和表长的比率叫做装填因子
二次探测：探测相隔较远的单元 步骤是步数的平方 问题：二次聚集
再哈希法：依赖关键字的探测序列 stepSize = constant * (key % constant)
链地址法：
哈希函数：快速计算、随机关键字
折叠：关键字分组
哈希化的效率：哈希函数的常量时间+探测长度
线性探测：成功的查询P=(1+1)/(1-L2)/2 失败的查询P=(1+1)/(1-L)/2
链表地址法：成功1+loadFactor/2 失败1+loadFactor
二次探测和再哈希法：成功log2(1-loadFactory)/loadFactory 失败1/（1-loadFactory）
开放地址法和链地址法的比较：容量已知、装填因子低于0.5 未知链地址法较好
哈希化和外部存储：索引
12.堆
优先级队列 插入和删除的时间复杂度都是logN 完全二叉树 每个节点的关键字都大于这个节点的子节点
弱序：不支持遍历 不支持查找关键字
移除：移走根 最后一个节点移动到根的位置 一直向下筛选
插入：向上筛选
不是真的交换 减少复制的次数
堆的效率：log2N
堆排序：复制次数比快速排序多、时间复杂度O（logN）
13.图
边和顶点
交叉点间的连通性 邻接 路径
连通图和非连通图
无向图
欧拉7桥问题