排序综合

堆排序

什么是堆？分为两类

  1. 大根堆
    顾名思义，满足完全二叉树，且父母节点永远比子节点要大
  2. 小根堆
    和上面的区别只在父母节点永远比子节点要小
    首先需要解决两个问题
  • 如何给一个无序变成有序？
  • 如何将堆顶元素排出之后还是一个堆？
    这里我们先解决第二个问题，第二个解决之后第一个问题将迎刃而解

    如何解？

    A2：将堆顶元素弹出之后，将最大的元素（最后一个）置于堆顶，然后依次递归变成叶子节点
    A1：（叶子节点就是堆）（方法是反复筛选）从最后找，找到第一个不是叶子的节点（n/2），然后依次从n/2—->到 1 依次调整即可，注意从上向下的必须调整到叶子才行
    补充一个小知识点：在完全二叉树中，一个节点序号为n，那么他的父母节点一定是n/2，即可以推出最后一个非叶子节点就是n/2
    堆排序算法性能分析：
  • 时间复杂度优势：稳定 一直都是O(nlog2(n))
  • 空间复杂度：不需要额外空间O(1)