14.5.4 选择类排序

选择类排序的核心不是“逐步插入”，而是“每趟选择一个最值”。如果按升序排列，第 1 趟从所有元素中选最小值放到第 1 个位置，第 2 趟从剩余元素中选次小值放到第 2 个位置，依次推进。

简单选择排序：每趟确定一个最终位置

以 57, 68, 59, 52 为例：

趟数	待排序区	选出的最小值	操作	结果
第 1 趟	57,68,59,52	52	与第 0 位交换	52,68,59,57
第 2 趟	68,59,57	57	与第 1 位交换	52,57,59,68
第 3 趟	59,68	59	已在正确位置	52,57,59,68

每趟都要扫描待排序区找到最小值，因此比较次数与初始序列是否有序关系不大：

$$(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$$

所以简单选择排序最好、平均、最坏时间复杂度通常都记为 $O(n^2)$。交换只需要一个临时变量，辅助空间是 $O(1)$。

为什么简单选择排序不稳定

简单选择排序会把远处的最小值直接换到当前位置，这种“隔空交换”可能让相等关键字的相对次序改变。

排序前：52a, 57, 52b, 40
第 1 趟选出 40，与 52a 交换
结果：40, 57, 52b, 52a

52a 原本在 52b 前面，交换后到了后面，因此不稳定。课程里把这种远距离交换称为判断不稳定性的直观线索。

堆排序：选择思想的结构化优化

简单选择每趟都线性扫描找最值，代价太高。堆排序的改进是：用完全二叉树形式维护“最值在堆顶”的结构。

堆类型	性质	堆顶含义
大顶堆	每个父结点都不小于它的孩子	当前最大值
小顶堆	每个父结点都不大于它的孩子	当前最小值

判断一个序列是否为堆时，按层序把序列填入完全二叉树，然后检查每个父子关系是否都满足大顶堆或小顶堆条件。只要有一组父子关系不满足，就不是堆。

flowchart TD
  A["80"] --> B["60"]
  A --> C["45"]
  B --> D["40"]
  B --> E["20"]
  C --> F["16"]
  C --> G["15"]

上图是大顶堆示意：每个父结点都大于或等于孩子。考试常给一个数组，让你判断它是不是大顶堆/小顶堆。

堆排序的过程

按升序排序时，常用大顶堆：

1. 把初始序列调整成大顶堆，最大值位于堆顶。
2. 将堆顶元素与堆尾元素交换，最大值进入最终位置。
3. 堆的有效范围缩小 1，对新的堆顶向下调整，恢复大顶堆。
4. 重复直到所有元素都有序。

flowchart LR
  A["无序序列"] --> B["建大顶堆"]
  B --> C["堆顶最大"]
  C --> D["堆顶与堆尾交换"]
  D --> E["缩小堆范围"]
  E --> F["向下调整恢复堆"]
  F --> C

堆排序为什么是 $O(n\log n)$？每次取走堆顶后，调整堆沿着树高向下走。完全二叉树高度约为 ${\log }_{2}n$，取堆顶需要重复 $n$ 次，因此主导项为 $n\log n$。辅助空间仍只需交换变量，是 $O(1)$。

技术迭代视角：从简单选择到堆排序

问题	简单选择排序	堆排序的改进	换来的代价
找最值	每趟线性扫描	堆顶直接给出最值	需要建堆和调整堆
时间复杂度	$O(n^2)$	$O(n\log n)$	过程更难手工模拟
空间复杂度	$O(1)$	$O(1)$	仍不稳定
稳定性	不稳定	不稳定	没有改善稳定性

课程强调：堆排序的具体完整过程通常不是软件设计师考试最核心要求，但大顶堆、小顶堆判断、复杂度和特点要掌握。

考试判断

• “每趟选择最小/最大记录”是简单选择排序。
• “每趟确定一个元素最终位置”选择类排序、冒泡排序都可能满足，要结合动作判断。
• “完全二叉树、大顶堆、小顶堆、堆顶”是堆排序信号。
• “最坏仍为 $O(n\log n)$ 且辅助空间 $O(1)$”常选堆排序。
• 选择类排序常见结论：简单选择与堆排序都不稳定。

单选

若希望在大规模内部排序中保持最坏时间复杂度 $O(n\log n)$，同时辅助空间为 $O(1)$，下列哪种算法更符合？

A直接插入排序B冒泡排序C归并排序D堆排序

本节小结

选择类排序的本质是“找最值并放到最终位置”。简单选择排序简单但每趟都要扫描，复杂度为 $O(n^2)$；堆排序用堆结构减少找最值的代价，把时间优化到 $O(n\log n)$，但稳定性并没有改善。