1. 不稳定
2. 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法
3. 递归
   1. 分治法
      1. 确定递归边界
   2. 折半查找法
      1. 前提有序
4. 二叉树
   1. 性质
      1. p116
   2. 遍历
      1. 先序遍历
         1. 根左右
      2. 中序遍历
         1. 左根右
      3. 后序遍历
         1. 左右根
      4. 层次遍历
         1. 使用队列
            1. 根结点入队
            2. 结点出队，左孩子入队，右孩子入队
   3. 堆
      1. 大顶堆
         1. 非叶子节点大于左右孩子节点
      2. 小顶堆
         1. 非叶子节点小于左右孩子节点
   4. 二叉查找树BST
      1. 左子树所有的值都小于根结点的值
      2. 右子树所有的值都大于根结点的值
      3. 左右子树都是二叉查找树
      4. 性能与高度成正比。最小为o(logn)，最大为o(n)
   5. 平衡二叉树AVL
      1. 保证高度最小，对BST的改进
5. 树
   1. 存储结构
      1. 双亲表示法
         1. 数据+双亲位置
      2. 双亲孩子表示法
         1. 数据+双亲位置+孩子结点指针
            1. 孩子结点链表
      3. 孩子兄弟表示法
         1. 第一个孩子+数据+下一个兄弟指针
            1. 兄弟结点链表
   2. 遍历
      1. 先序遍历
         1. 根左右
      2. 中序遍历
         1. 因为子结点数目不确定所有不考虑
      3. 后序遍历
         1. 左根右
   3. 并查集
      1. p158
   4. B树
6. 图
   1. 遍历
      1. 深度优先遍历
         1. 往深走，走不通就回来
      2. 广度优先遍历
         1. 按层次访问
   2. 最小生成树
      1. 权值之和最低
         1. 普里姆算法
            1. 找到已经连接的节点中与未连接结点最短的边
         2. 克鲁斯卡尔算法
            1. 选全部边里面最短的边，再判断是否产生回路
7. 哈希表
   1. 哈希构造
      1. 直接定址法
         1. 关键字自身为哈希
         2. 很少关键字是连续的 浪费空间需要平移
      2. 除留余数法
         1. 取模
      3. 数字分析法
         1. 找到规律
      4. 折叠法
         1. 关键字分开几个区间加起来获得几位
      5. 平方取中法
         1. 平方关键字再取中间几位
   2. 处理冲突的方法
      1. 开放定址法
         1. 寻找下一个可用地址
         2. 线性探测法
            1. 加一再取模
         3. 二次探测法
            1. 加1....K的平方
            2. 减少堆聚
      2. 链地址法
         1. 每个地址形成一个子链
8. 排序
   1. 直接插入排序
      1. 从无序区找到一个记录插入到有序区
         1. o(n²)
   2. 选择排序
      1. 遍历整个序列找到最小的放到最前面
   3. 希尔排序
      1. 对直接插入排序的改进
         1. 每隔一个增量选出一个元素放到一个区间 每个区间进行直接插入排序 做完后缩小增量 逐渐合成一个区间
         2. 可以实现宏观上的调整 移动距离远
   4. 基数排序
      1. 多关键字排序
         1. 高位优先排序
            1. 最高关键字划分子序列，再对子序列进行次关键字的排序
         2. 低位优先排序
            1. 从最低关键字开始划分，不产生子序列，每趟都是对整个序列进行排序
            2. 需要稳定的算法
      2. 基数排序
         1. 从最低位开始排序
            1. o(n) 快
         2. 链式
            1. 分配：分配的不同的子序列 收集：从小到大连接序列
         3. 计数
            1. 每一趟只比较低关键字，先确定每个子序列的起始位置，再根据位置复制到新空间的合适位置
   5. 归并排序
      1. 将待排序序列拆成有序子序列（最后到只有2个元素的序列）再合并起来
         1. o(nlogn)
   6. 快速排序
      1. 将序列划分成 枢轴+其余部分
         1. 排序成 比枢轴小+枢轴+比枢轴大 再进行子序列递归
   7. 堆排序
      1. 建一个大顶堆，获得最大的堆顶，将堆顶与堆尾交换位置，长度减一，再次调整成大顶堆
         1. 建堆o(n)，最坏复杂度o(nlogn)
9. 线性数据结构
   1. 顺序栈
      1. 应用
         1. 数值转换
         2. 括号匹配
   2. 循环队列
   3. 顺序表
      1. 可以在任意位置进行操作
         1. 存储位置表示前驱和后继关系
      2. 只在表头表尾操作
         1. 栈表
      3. 应用
         1. 一元稀疏多项式操作
         2. 稀疏矩阵压缩
            1. 三元组顺序表
            2. 行列值
   4. 链栈与链队列
   5. 线性表的链式表示和实现
      1. 单链表
      2. 双向链表
      3. 循环链表
   6. 采用连续存储结构
   7. 采用链式存储结构