软考-软件设计师：排序算法-选择类排序：直接选择排序、堆排序 作者：马育民 • 2025-04-15 08:55 • 阅读：10004 # 直接选择排序 1. 先取出所有记录中最小的记录，将其与第1个记录互换 2. 在剩下的记录中，选出最小的记录，与第2个记录交换 3. …以此类推，直到排序结束 ### 例子 将 `T=(21,25,49,27,16,08)` 进行排序 第1趟：先取出最小值 `08`，与第 `1` 个元素交换位置，结果： `【08】,25,49,27,16,21` 第2趟：在 **剩下的元素** 中，取出最小值 `16`，与第 `2` 个元素交换位置，结果： `【08,16】,49,27,25,21` 第3趟：同上，结果：【08,16,21】,27,25,49 第4趟：同上，结果：【08,16,21,25】,27,49 第5趟：**不需要找最小值**，结果：【08,16,21,25,27】,49 ### 时间复杂度 O(n²) 过程：n个元素，最后一次不用选最小值，前几次比较元素需要比较 `n` 次，总共：`n(n-1)` 次，渐进表示：`O(n²)` **基本有序的情况：**也是 `O(n²)`，因为每次都会比较 ### 空间复杂度 O(1) ### 是否稳定 不稳定 ### 优点 简单，好理解 # 堆排序 ### 什么是 堆 设有 `n` 个元素的序列 `{K1，K2，... ，Kn}`，当且仅当满足下述关系之一时，称之为 **堆**： - 满足 $$K\_i <= K\_{2i}$$ 且 $$K\_i <= K\_{2i+1}$$ ，此时叫小根堆。 - 满足 $$K\_i>=K\_{2i}$$ 且 $$K\_i >= K\_{2i+1}$$ ，此时叫大根堆。 **提示：**其中 `2i` 和 `2i+1` 应不大于 `n` **提示：** 元素 $$K\_i$$、$$K\_{2i}$$、$$K\_{2i}$$ 的关系如下： [](https://www.malaoshi.top/upload/0/0/1GWwY22MlbY.png) ### 小根堆 和 大根堆 图 如下图： [](https://www.malaoshi.top/upload/0/0/1GWwYvCxMA8.png) **小根堆：**父结点比左孩子、右孩子小 **大根堆：**父结点比左孩子、右孩子大 ### 排序思想 先将 `原始序列` 调整为 `堆序列`，然后得到 `堆顶元素`，再将剩下的序列重新调整为堆-- `重构堆`，得到此时的堆顶元素，依此类推，直到所有元素均输出为止，此时元素 `输出的序列` 就是 `一个有序序列` ### 排序过程 堆排序的算法步骤如下(以 **大顶堆** 为例）： 1. 初始时将顺序表 `R[1..n]` 中元素建立为一个大根堆，堆顶位于 `R[1]`（**第一个元素是堆顶，也就是根**），待序区为 `R[1..n]` 2. 循环执行 `步骤3～步骤4`，共 `n-1` 次。 3. 假设为第 `i` 运行，则待序区为 `R[1..n-i+1]` ，将堆顶元素 `R[1]` 与待序区尾元素 `R[n-i+1]` 交换，此时顶点元素被输出，新的待序区为 `R[1..n-i]` 4. 待序区对应的堆已经被破坏，将之重新调整为大根堆。 ### 优点 对于大量的记录来说，堆排序的效率很高。 ### 例子 将序列 `（55,60,40,10,80,65,15,5,75）` 进行堆排序 ##### 建立初始大根堆 将待排序的关键字分到一棵 **完全二叉树** 的各个结点中： - **根是第1个元素** - 第2层是 第 `2`、`3` 元素 - 第3层是 第 `4-7` 元素 - ...以此类推 （此时完全二叉树并不一定具备堆的特性） 如果 **父元素比子元素小，就交换位置**，过程如下图： [](https://www.malaoshi.top/upload/0/0/1GWwa2Wt5T7.png) ##### 找到最大值 初始大根堆后，根节点就是最大值 ##### 调整为新堆 1. 将 **最后一个叶子节点** 放到 **根节点** 的位置，此时堆已经被破坏 2. 将其重新调整为大根堆 ##### 重复上面过程 直到全部排序为止 [](https://www.malaoshi.top/upload/0/0/1GWwamsKk6J.png) ##### 总结 [](https://www.malaoshi.top/upload/0/0/1GWwatQPhXC.png) ### 时间复杂度 堆排序的整个算法时间是由建立初始堆和不断调整堆这两部分时间构成的。 时间复杂度为 `O(nlogn）` ### 空间复杂度 堆排序只需要一个记录大小的辅助空间，空间复杂度是：`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 原文出处：http://malaoshi.top/show_1GWwqJ9GRAF.html