本文介绍堆排序的思想和代码
- 参考链接:堆排序【超详细+代码】
基本思想
- 生成最大堆(heapify):从倒数第一个非叶节点开始,按照下虑操作找到该节点在最大堆中的位置,逐步遍历每一个非叶结点执行上述操作,生成最大堆
- 交换最大值到末尾:交换根节点与最后一个元素的值,树节点减少1(刚才根节点是当前树的最大值,更换以后就是有序的元素了,不再参与最大堆调整)
- 重新生成最大堆(调整根节点):调整新换上来的根节点(下虑操作),找到其应该在的地方,重新生成最大堆
- 循环交换根节点和调整根节点这两个步骤,直到最大堆只剩下一个元素
代码实现
1 | // 堆排序实现,对长度为n的数组a进行排序 |