堆排序(Heap Sort)

选择排序每次选出一个最大值—->优化 堆排序


image.png
下标为i的节点的父节点下标:(i-1) / 2
下标为i的节点的左孩子下标:i 2 + 1
下标为i的节点的右孩子下标:i
2 - 1

堆排序过程:
①对数据进行原地建堆(heapify)
②重复以下操作,直到元素数量为1

  • 交换堆顶元素和尾元素
  • 堆的元素数量减1
  • 对0的位置进行1此SiftDown。

快速排序

image.png

时间复杂度分析:
image.png