数据结构第八章排序

数据结构第八章 排序 （知识点提醒）直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、多路归并排序（数据太多，内存不够用，用到磁盘（外存）

排序

• 基本概念
  • 稳定性
  • 衡量标准：时、空复杂度
• 内部排序
  • 插入排序
    • 直接插入排序
    • 折半插入排序
    • 希尔排序
      • 步长增量d 逐趟减为1
  • 交换排序
    • 冒泡排序
    • 快速排序
      • 分治的思想
  • 选择排序
    • 简单选择排序
    • 堆排序
      • 历年重点
      • 大顶堆、小顶堆
      • 堆的创建与删除顶点
  • 归并排序
  • 基数排序
• 外部排序
  • 多路归并排序（数据太多，内存不够用，用到磁盘（外存）
    • 多路归并
    • 败者树
    • 置换选择算法
      • 有限缓冲区得到尽可能长的归并段
    • 最佳归并树（哈夫曼思想）