堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的值总是小于（或者大于）它的父节点。

算法步骤

  1. 将初始待排序列 (R1,R2,…,Rn) 构建成大顶堆，此堆为初始的无序区；

  2. 将堆顶元素 R1 与最后一个元素 Rn 交换，此时得到新的无序区 (R1,R2,…,Rn−1) 和新的有序区 Rn, 且满足 Ri⩽Rn(i∈1,2,…,n−1)；

  3. 由于交换后新的堆顶 R1 可能违反堆的性质，因此需要对当前无序区 (R1,R2,…,Rn−1) 调整为新堆，然后再次将 R1 与无序区最后一个元素交换，得到新的无序区 (R1,R2,…,Rn−2) 和新的有序区 (Rn−1,Rn)。不断重复此过程直到有序区的元素个数为 n−1，则整个排序过程完成。

图解算法

HeapSortHeapSort

代码实现

算法分析

  • 稳定性：不稳定

  • 时间复杂度：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)

  • 空间复杂度：O(1)