数据结构第八章_sort

数据结构思维导图，包含插入排序、 交换排序、 选择排序、外部排序、 基数排序等。

第八章 sort

• 插入排序
  • 直接插入排序
    • 每次将一个待排序的纪录按照关键字大小插入已经排好的子序列，直到全部记录插入完成。
    • 空间效率O（1）
    • 时间效率O
      • 最好O（n），只需要比较n-1次
      • 最坏O（n平方）
      • 平均O（n平方）
      • 比较次数与表的初始状态有关
    • 稳定性
      • 稳定
    • 适用性
      • 顺序存储和链式存储的线性表 基本有序和数量不大的排序表
  • 折半插入排序
    • 空间效率O（1）
    • 时间效率
      • 最好O（nlog2n）
      • 最坏O（n平方）
      • 平均O（n平方）
      • 比较次数仅与表中元素个数n有关
    • 稳定性
      • 稳定
    • 适用性
      • 顺序存储的线性表
  • 希尔排序shell （缩小增量排序）
    • 相隔增量d的纪录化为子表，对各个子表进行直接插入排序，基本有序后进行一次直接插入排序
    • 空间效率O（1）
    • 时间效率
      • 最好O的1.3次方
      • 最坏O（n平方）
    • 稳定性
      • 不稳定
    • 适用性
      • 顺序存储的线性表
• 交换排序
  • 冒泡排序
    • 空间效率O（1）
    • 时间效率
      • 最好O（n）比较次数为n-1，移动次数0
      • 最坏O（n平方） 待排表为逆序，需进行n-1次排序 第i趟要进行n-1次关键字比较， 每次比较后移动3次交换元素位置
      • 平均O（n平方）
    • 稳定性
      • 稳定
    • 适用性
      • 顺序存储和链式存储的线性表 元素个数不是很大
  • 快速排序
    • 空间效率
      • 最好O（log2n）
      • 最坏O（n）进行n-1次递归调用
      • 平均栈的深度为O（log2n）
    • 时间效率
      • 最坏O（n平方） 枢轴划分的两个区域分别为n-1和0个元素时
      • 最好O（nlog2n） 快速排序是所有内部排序算法中平均性能最优的
      • 平均O（nlog2n）
    • 稳定性
      • 不稳定
    • 适用性
      • 顺序存储的线性表
• 选择排序
  • 简单选择排序
    • 空间效率O（1）
    • 时间效率
      • O（n平方） 元素间比较次数始终为n（n-1）/2
    • 稳定性
      • 不稳定
    • 适用性
      • 顺序存储和链式存储的线性表 关键字较少的情况
  • 堆排序
    • 空间效率O（1）
    • 时间效率
      • 建堆时间为O（n） 每次调整时间复杂度O（h），n-1次向下调整
      • 最好最坏平均O（nlog2n）
    • 稳定性
      • 不稳定
    • 适用性
      • 顺序存储的线性表
• 二路归并排序
  • 二路归并排序
    • 空间效率O（n）
    • 时间效率
      • 每趟归并时间复杂度O（n） 共需进行log2n向上取整次归并
      • O（nlog2n）
    • 稳定性
      • 稳定
    • 适用性
      • 顺序存储和链式存储的线性表
  • 多路归并排序
    • 对N个元素进行Ｋ路归并时，排序的趟数m满足k的m次方=N，m=logkN向上取整
• 基数排序
  • 基数排序
    • 空间效率O（r） r个队列：r个队头和队尾指针
    • 时间效率O（d（n+r）） 一趟遍历O（n），一趟收集O（r）
    • 稳定性
      • 稳定
    • 适用性
      • 顺序存储和链式存储的线性表
  • 计数排序
• 外部排序
  • 多路平衡归并
  • 败者树
    • k路归并的败者树深度为log2k向上取整+1
    • 从k个记录中选择最小关键字， 进行log2k向上取整次比较
  • 置换—选择排序
    • 生成初始归并段
  • 最佳归并树
    • 倒立的哈夫曼树 WPL带权路径长度最小
    • 需添加0的虚段
    • （n0-1）%k-1 n0几个归并段，k几叉树