1. 基本排序

  • 冒泡

  • 插入

    1.1 冒泡

    依次移动
    没有交换，则排好序
    空间复杂度O(1)
    时间复杂度 O(n^2) 最好O(n)
    稳定 数组中两个数排序后相对位置不变

    1.2 插入排序

    • 空间复杂度 O(1)
    • 时间复杂度 已排好O(n) 逆序和杂乱无章 O(n)

    • leedcode 147

      2. 常考排序

      2.1 归并

    • 核心思想是分治

    • 首先递归 然后融合
    • image.png
    • image.png
    • image.png

    • 练熟

      2.2 快排

    • image.png

    • image.png
    • image.png

最复杂情况类似冒泡排序了，为O(n^2)，因此随机选择基准值

  • image.png

  • leedcode 215

    2.3 拓扑排序

  • 用来理清有依赖关系的任务

  • image.png
  • image.png
  • 首先计算各个节点的入度，逐个删除入度为0的点
  • 构建图
  • image.png

    3. 其他排序算法

  • 堆排序
  • 桶排序