了解堆的操作和向上（下）调整算法可以看我的上一篇文章：
堆是什么？
堆排序，堆排序，首先就要知道堆是什么
堆是顺序存储逻辑结构是二叉树的特殊数据结构
如下图：
了解堆的操作和向上（下）调整算法可以看我的上一篇文章：
堆排序的原理
根据堆的特点：
堆只有大堆（大顶堆）和小堆（小顶堆）
大堆：左右孩子节点中存储的数据都必须小于等于父亲节点，根节点最大
小堆：左右孩子节点中存储的数据都必须大于等于父亲节点，根节点最小
可知大（小）堆堆顶的数据一定是堆中存储的所有元素中最大（小）的
所以我们只需要将堆顶数据（顺序表第一个元素）和堆的最后一个元素交换（顺序表最后一个元素），
堆中的最大（小）的元素就到了顺序表的最后
虽然交换之后的顺序表不是堆了，但是只需要将交换到堆顶的数据，进行一次向下调整算法，得到的就又是一个大（小）堆，而且一次向下调整算法的时间复杂度只有O（logN）
再将顺序表的倒数第二个元素当做新的最后一个元素,与调整后新的堆顶换…………
如此循环
我们就可以得到一个有序表了
由上得：
排升序，建大堆
排降序，建小堆
如何建堆？怎样建堆更快？
根据堆排序的原理可得：
实现对排序之前，要先将要排序的数据建堆
那么如何建堆？
有两个方法建堆
1.使用向上调整算法建堆
将要排序的数据从头到尾一个一个进行向上调整算法即可
时间复杂度分析
由上图得：
每一层的节点向上调整的最大次数不一样，所以要分开加算
总的调整次数为F（h）：
F(h)=20 X 0+ 21 X 1+22 X2+…………+2(h-1) X(h-1)
使用错位相减法后，化简得：
F(h)=2h X(h-2)+2
由完全二叉树的特性得：
h=log N
2h-1=N
带入F（h）得
F（h）=(N+1)*(logN-2)+2
所以时间复杂度为：O(N*logN)
2.使用向下调整算法建堆
从最后一个非叶子节点开始调整，调整到顺序表第一个元素（下标为0的元素）
时间复杂度分析
总的调整次数为F（h）：
F（h）=20 x(h-1) +21 x(h-2)+…………+2(h-2)x1+2(h-1)x0
使用错位相减法后，化简得：
F(h)=2h-1-(h-1)
由完全二叉树的特性得：
h=log N
2h-1=N
带入得
F（N）=N-logN
所以时间复杂度为：O（N）
结论：使用向下调整算法建堆更好
堆排序的实现
堆排序的时间复杂度
如下图：
所以堆排序总的时间复杂度为O(N*logN)
堆排序的稳定性
堆排序并不是一个稳定的排序算法
在堆排序的过程中，当交换了堆顶元素后，进行向下调整时，有可能破坏了相同元素之间的稳定性。
例如，第n/2个父节点可能交换了后面一个元素，而第n/2-1个父节点没有交换后面一个相同的元素，这样就破坏了这两个相同元素之间的稳定性。
以上就是全部内容了，如果对你有帮助的话可以点赞收藏支持一下！
