排序类算法思维导图

常见排序算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

排序类算法

• 讨论的算法
  • 快排序
  • 希尔排序
  • 归井
  • 堆排序
  • 平均O（N*logN）
  • 插入
  • 选择
  • 冒泡
  • 平均O（N*N)
• 算法的分类
  • 分治
    • 归井算法
    • 快排
  • 基于插入
    • 希尔排序
    • 直接插入算法
  • 基于选择
    • 堆排序
    • 直接选择排序
• 算法的稳定性
  • 稳定算法
    • 归井
    • 插入
    • 冒泡
  • 不稳定
    • 堆排序
    • 快排序
    • 希尔
    • 选择
• 算法与数据的关系
  • 数据不敏感
    • 归井排序
    • 选择排序
    • 堆排序
  • 数据敏感
    • 冒泡
    • 快排序
    • 插入排序
    • 希尔排序
• 算法的空间特性
  • 需要使用堆栈或者递归实现
    • 快排
    • 希尔
    • O(N*LogN）
  • 常数空间复杂度
    • 堆排序
    • 归井排序
    • O(N*LogN)
    • 插入
    • 冒泡
    • 选择
    • O(N*N)