堆排序

学习数据结构与算法
2021-05-17 14:29 · 阅读时长3分钟
小课

堆排序是基于二叉堆的一种排序算法,建议先了解一下什么是堆,最大堆和最小堆,这样理解起来会更容易。堆排序的最好、最坏以及平均时间复杂度都是O(NlogN)。

算法主要思路是

  1. 构建一个最大堆(或者最小堆),参考二叉堆课程。
  2. 从最大堆中取出第一个元素arr[0],也就是最大的元素,与数组最后一个元素arr[size-1]交换。
  3. 对数组中第一个元素执行下移操作,使得arr[0, size-1]子数组仍然是最大堆。
  4. 重复第2步,直到最大堆中所有元素取完。

下面以数组[1, 3, 2, 5, 6, 4]为例,选择使用最大堆排序。

查看二叉堆课程

注释
加载中...
堆排序排序算法二叉堆