软考-软件设计师：排序算法-选择类排序：堆排序 作者：马育民 • 2026-02-03 15:38 • 阅读：10007 # 说明 堆排序是借助 **堆** 来实现的 **选择排序**，思想同简单的选择排序，以下以大顶堆为例。 **注意：**如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。 **一句话解释：**存储堆的数组，是无序的；堆排序后，数组是有序的（升序或降序） 下图是堆：  数组是： ``` [100,33,8,11,5,6,3,7] // 数组无序 ``` 下图是堆排序后的结果：  数组是： ``` [3,5,6,7,8,11,33,100] // 数组有序 ``` # 过程 1. 先将 `原始无序的序列` 调整为 `堆` 2. 然后将 `堆顶元素` 交换至堆末尾 3. 再将剩下的序列重新调整为堆-- `重构堆` 4. 然后将 `堆顶元素` 交换到堆末尾第2个元素 5. 依此类推，直到所有元素均输出为止，此时 `输出的序列` 就是 `一个有序序列` # 优点 对于大量的记录来说，堆排序的效率很高。 # 例子 堆无序数列 `{100,5,3,11,6,8,7}` 进行堆排序（升序） 将数组放到完全二叉树中：  ### 建大顶堆 操作详见[链接](https://www.malaoshi.top/show_1GW2iX24hVDb.html "链接")  ### 堆排序第1步 首先将堆顶元素 `100` 交换至 `最底部7` 的位置，`7` 升至堆顶 `100` 所在的底部位置即为有序区，有序区不参与之后的任何对比。  ### 堆排序第2步 在 `7` 升至顶部之后，**对顶部重新做最大堆调整**，左孩子 `33` 代替 `7` 的位置。  ### 堆排序第3步 在 `7` 被交换下来后，下面还有子节点，所以需要继续与子节点对比，左孩子 `11` 比 `7` 大，所以 `11` 与 `7` 交换位置，交换位置后 `7` 下面为有序区，不参与对比，所以本轮结束，无序区再次形成一个最大堆。  ### 堆排序第4步 将最大堆堆顶 `33` 交换至 `堆末尾第2个位置`，扩大有序区  ### 堆排序第n步 重复上面的步骤，不断建立最大堆，并且扩大有序区，最终全部有序。  数组是： ``` [3,5,6,7,8,11,33,100] // 数组有序 ``` ### 总结 [](https://www.malaoshi.top/upload/0/0/1GWwatQPhXC.png) # 时间复杂度 堆排序的整个算法时间是由建立初始堆和不断调整堆这两部分时间构成的。 平均时间复杂度：$$O(n\log\_2n)$$ 最好时间复杂度：$$O(n\log\_2n)$$ 最差时间复杂度：$$O(n\log\_2n)$$ ### 为什么最好、最差、平均是一样的 堆化永远是 O (log n) 排序永远要做 n-1 次堆化 与数据初始顺序无关（不像快排会退化到 O (n²)） # 空间复杂度 堆排序只需要一个记录大小的辅助空间，空间复杂度是：`O(1)` # 是否稳定 不稳定，重建堆时，直接讲尾部元素放到根结点位置 # 题 对数组A=(2,8,7,1,3,5,6,4） 构建大顶堆为 ( )（用数组表示） A、(1,2,3,4,5,6,7,8) B、(1,2,5,4,3,7,6,8) C、(8,4,7,2,3,5,6,1) D、(8,7,6,5,4,3,2,1) ### 分析 1.构建大顶堆，那么根结点（第一个元素）是最大值，所以排除 A、B 2.前三个元素 `2、8、7` 构建大顶堆过程： [](https://www.malaoshi.top/upload/0/0/1GWwghR7JxN.png) 所以 `7` 的位置没变，所以选择 C ### 答案 C 参考： https://zhuanlan.zhihu.com/p/124885051 原文出处：http://malaoshi.top/show_1GW2iXilu7Cn.html