数据结构 图和排序

关于数据结构 图和排序的思维导图，如 排序：1.直接插入排序：哨兵=1，小才交换；2.希尔排序：相差dk比较，不稳定 ；3.冒泡排序 相邻两两比较 for（i <=n）for(j<=n-i)，稳定；4.交换排序；5.简单选择排序 遍历找最值放一端 ... ...

数据结构

• 线性表
• 树
  • 线索二叉树
  • 哈夫曼树
• 图
  • 1. 基本概念
    • I. 无向 n(n-1)/2
    • II. 有向 n(n-1)
    • III. 连通图n-1
    • IV. 强连通图n
  • 2. 存储
  • 3. 遍历
    • 广度bfs 一点占头
      • 层次+队列（原地先爆孩子
    • 深度dfs 一点到头
      • 先序+栈（走到最低，弹出爆孩子
  • 4. 最小生成树（无环）
    • prim普里姆算法 （树）
      • 一点从小到大权值
    • kruskal克鲁斯卡尔算法 （森林）
      • 整张图 小到大
  • 5. 最短路径 有向带权
    • Dijkstra算法
      • 每次终点集到外部最小
        • O(n²)（邻接矩阵、邻接表）
    • Floyd算法
      • 分别以某个点为中介 比较直接到达最小
  • 6. 拓扑排序 重复选头节点（判断无环）
  • 7. 关键路径：AOE网 V事件点 a活动边
    • Ve事最早开始，时间最长最大值
    • Vl事最晚开始，时间最短最小值
    • e=ve（出来的）活动最早 前面的事
    • l=Vl（指向的）-a自身
• 查找
• 排序
  • 1. 直接插入排序：哨兵=1，小才交换
    • o(n^2) o(1)
  • 2. 希尔排序：相差dk比较，不稳定
    • O(nlog2n) o(1)
  • 3. 冒泡排序 相邻两两比较 for（i <=n）for(j<=n-i)。稳定
    • o(n^2) o(1)
  • 4. 交换排序
    • I. 快速排序 1拿走当界点 分别lh比较 交换位置 相等放回去 类似优化mid=pivotloc折半. 不稳定
      • O(nlog2n) o(log2n)
  • 5. 简单选择排序 遍历找最值放一端
  • 6. 堆排序 大根 小根 判定 建立 调整
    • 调整 最大最小交换 输出 下坠交换
    • O(nlog2n)
  • 7. 归并排序 11 =2 2=11 空间要求最大
    • O(nlog2n)
  • 8. 基数排序 个十百位数排序 不稳定
  • 排序知识点小结
    • 时间复杂度
      • 快希nlog2n归堆
    • 空间复杂度
      • 归并n
    • 稳定性
      • 情绪不稳定，快希选堆好朋友聊天
• 数组与广义表
• 栈和队列
• 题目非连通图，结点+1