考点频率★★★★★数据结构必考选择题常考堆的性质与建堆过程简单选择排序常考时间复杂度难度⭐⭐⭐⭐简单选择排序简单堆排序需要重点理解堆的调整过程建议重点掌握简单选择排序的时间复杂度与稳定性重点掌握堆的定义大根堆/小根堆、建堆过程与堆排序流程1️⃣ 什么是选择类排序选择类排序的核心思想是每一轮从待排序序列中选出最小或最大的元素放到已排序序列的末尾。打个比方你有一堆大小不一的石头要从小到大排列。你每次都从剩下的石头中找出最小的那颗放到已经排好的石头堆后面。重复这个过程直到所有石头都排完。两类最经典的选择排序算法核心策略一句话概括简单选择排序每轮扫描剩余序列选最小元素放到前面“每轮找最小的放到最前面”堆排序利用堆完全二叉树快速找到最大/最小元素“用堆结构加速选择”2️⃣ 简单选择排序2.1 核心思想每一轮从待排序序列中选出最小的元素放到已排序序列的末尾。voidSelectionSort(intarr[],intn){for(inti0;in-1;i){intminIdxi;for(intji1;jn;j){if(arr[j]arr[minIdx]){minIdxj;}}if(minIdx!i){Swap(arr[i],arr[minIdx]);}}}2.2 执行过程示例对数组[5, 3, 8, 1, 4]进行简单选择排序轮次未排序部分最小元素交换后结果初始[5, 3, 8, 1, 4]——第1轮[5, 3, 8, 1, 4]1下标3[1, 3, 8, 5, 4]第2轮[3, 8, 5, 4]3下标1[1, 3, 8, 5, 4]第3轮[8, 5, 4]4下标4[1, 3, 4, 5, 8]第4轮[5, 8]5下标3[1, 3, 4, 5, 8]2.3 复杂度与特点情况时间复杂度说明最好情况O(n2)O(n^2)O(n2)即使有序仍需扫描找最小值最坏情况O(n2)O(n^2)O(n2)与最好情况相同平均情况O(n2)O(n^2)O(n2)与最好情况相同空间复杂度O(1)O(1)O(1)原地排序稳定性❌不稳定交换操作可能改变相等元素的相对顺序如[2, 2, 1]第一轮会将第一个2与1交换两个2的相对顺序被破坏关键特点简单选择排序的比较次数与初始序列无关始终为n(n−1)/2n(n-1)/2n(n−1)/2次。3️⃣ 堆排序Heap Sort3.1 什么是堆堆Heap是一种特殊的完全二叉树满足以下条件类型条件用途大根堆Max Heap任意节点的值 ≥ 其子节点的值升序排序每次取堆顶最大值小根堆Min Heap任意节点的值 ≤ 其子节点的值降序排序每次取堆顶最小值堆的存储用数组存储完全二叉树下标从111开始或从000开始软考中下标从1开始更常见。数组下标从111开始时节点iii的左子节点为2i2i2i右子节点为2i12i12i1父节点为⌊i/2⌋\lfloor i/2 \rfloor⌊i/2⌋。3.2 堆排序的核心思想堆排序利用堆结构快速找到最大或最小元素分为两步建堆将无序序列构建成一个大根堆或小根堆排序反复取出堆顶元素最大值放到数组末尾然后对剩余元素重新调整成堆打个比方你有一堆大小不一的石头想从大到小排列。你先花点功夫把所有石头按“父大子小”的规则堆成一个“金字塔”建堆。然后每次从塔顶拿走最大的石头堆顶把剩下的石头重新调整成金字塔堆调整。这样每次都能拿到剩余石头中最大的不用每次都扫描所有石头。3.3 建堆过程核心考点建堆的步骤将待排序序列看作一棵完全二叉树从最后一个非叶子节点开始依次向前调整使每个子树都满足堆的性质最后一个非叶子节点的位置n/2n/2n/2下标从111开始建堆示例将序列[4, 10, 3, 5, 1, 2, 8]建成大根堆初始完全二叉树 4 / \ 10 3 / \ / \ 5 1 2 8 节点编号从1开始1:4, 2:10, 3:3, 4:5, 5:1, 6:2, 7:8 n7最后一个非叶子节点 7/2 3节点3值为3调整过程步骤调整节点操作结果1节点3值3子节点为6(2)、7(8)8最大且3交换3和8节点3变为8节点7变为32节点2值10子节点为4(5)、5(1)10最大无需交换不变3节点1值4子节点为2(10)、3(8)10最大且4交换1和2节点1变为10节点2变为44节点2值4子节点为4(5)、5(1)5最大且4交换2和4节点2变为5节点4变为4最终大根堆10 / \ 5 8 / \ / \ 4 1 2 3数组表示[10, 5, 8, 4, 1, 2, 3]3.4 堆排序过程建堆完成后排序过程如下将堆顶最大值与堆的最后一个元素交换堆的大小减1对新的堆顶进行向下调整重新满足堆的性质重复步骤1-3直到堆中只剩1个元素示例接上面的建堆结果步骤堆顶交换到末尾调整后的堆初始10—[10, 5, 8, 4, 1, 2, 3]第1次10 与 3 交换[3, 5, 8, 4, 1, 2, 10][8, 5, 3, 4, 1, 2, 10]第2次8 与 2 交换[2, 5, 3, 4, 1, 8, 10][5, 4, 3, 2, 1, 8, 10]第3次5 与 1 交换[1, 4, 3, 2, 5, 8, 10][4, 2, 3, 1, 5, 8, 10]…………最终得到升序序列[1, 2, 3, 4, 5, 8, 10]3.5 复杂度与特点情况时间复杂度说明最好情况O(nlog⁡n)O(n \log n)O(nlogn)建堆O(n)O(n)O(n)排序O(nlog⁡n)O(n \log n)O(nlogn)最坏情况O(nlog⁡n)O(n \log n)O(nlogn)同最好平均情况O(nlog⁡n)O(n \log n)O(nlogn)同最好空间复杂度O(1)O(1)O(1)原地排序仅需几个临时变量稳定性❌不稳定堆顶与末尾元素交换时可能改变相等元素的相对顺序4️⃣ 简单选择 vs 堆排序完整对比表重点对比项简单选择排序堆排序核心策略每轮扫描剩余序列找最小利用堆结构快速找最大/最小最好时间复杂度O(n2)O(n^2)O(n2)O(nlog⁡n)O(n \log n)O(nlogn)最坏时间复杂度O(n2)O(n^2)O(n2)O(nlog⁡n)O(n \log n)O(nlogn)平均时间复杂度O(n2)O(n^2)O(n2)O(nlog⁡n)O(n \log n)O(nlogn)空间复杂度O(1)O(1)O(1)O(1)O(1)O(1)稳定性❌ 不稳定❌ 不稳定比较次数与初始状态是否相关无关始终为n(n−1)/2n(n-1)/2n(n−1)/2相关建堆调整次数与初始序列有关适用场景数据量小、对稳定性无要求数据量大、追求高效排序5️⃣ 经典例题例题1堆的定义以下哪个序列可以构成一个大根堆A.[10, 7, 8, 5, 6, 4, 3]B.[10, 7, 8, 5, 6, 9, 3]C.[10, 7, 8, 5, 6, 4, 9]D.[10, 7, 8, 5, 6, 4, 11]解析大根堆要求每个节点的值 ≥ 其子节点。检查各选项A10≥7,87≥5,68≥4,3 → ✅ 全部满足B节点3值8的子节点为4和98≥9❌ 不满足C节点2值7的子节点为4和97≥9❌ 不满足D节点1值10的子节点为2和1110≥11❌ 不满足选A。例题2堆排序过程用堆排序对序列[3, 6, 5, 8, 2, 1, 7]进行升序排序建堆后大根堆的数组为 。解析n7最后一个非叶子节点为 7/2 3节点3值5调整节点35的子节点为6(1)、7(7)7最大且5 → 交换5和7调整节点26的子节点为4(8)、5(2)8最大且6 → 交换6和8调整节点13的子节点为2(8)、3(7)8最大且3 → 交换3和8继续向下调整节点2值3子节点为4(6)、5(2)63 → 交换3和6最终建堆结果[8, 6, 7, 3, 2, 1, 5]答案[8, 6, 7, 3, 2, 1, 5]6️⃣ 记忆口诀选择排序分两种简单堆排要分清。简单选择每轮扫O(n2)O(n^2)O(n2)不变样。堆排先建大根堆堆顶最大末尾归。向下调整保堆性O(nlog⁡n)O(n \log n)O(nlogn)效率高。7️⃣ 小测验评论区对答案序列[1, 5, 4, 8, 2, 6, 3]要建成大根堆需要从哪个节点开始调整A. 节点 1B. 节点 2C. 节点 3D. 节点 4本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #选择排序 #堆排序 #排序算法 #数据结构 #软考备考