DS-07-04 选择排序

408 > ### 数据结构 > #### 选择排序（简单选择排序/堆排序）

---

一、定位信息

维度	内容
章节归属	第7章 排序
知识单元编号	DS-07-04
前置知识	DS-07-01 排序基本概念、树与二叉树（堆的概念）
后续衔接	DS-07-09 排序算法综合对比
考试大纲要求	掌握简单选择排序和堆排序的算法思想、实现及性能分析
预计学习时长	50分钟

---

二、知识点讲解

1. 简单选择排序（Simple Selection Sort）

1.1 基本思想

简单选择排序的核心思想是每趟从待排序的无序区中选出关键字最小的元素，将其与无序区的第一个元素交换，使得有序区增加一个元素，无序区减少一个元素。

1.2 伪代码实现

void SelectSort(ElementType A[], int n) {
    // 简单选择排序，A[0..n-1]
    int i, j, min;  // min 记录最小元素下标
    for (i = 0; i < n - 1; i++) {  // 共需 n-1 趟
        min = i;  // 假设当前无序区第一个元素最小
        for (j = i + 1; j < n; j++) {  // 在无序区中找最小元素
            if (A[j].key < A[min].key)
                min = j;  // 更新最小元素下标
        }
        if (min != i)  // 若最小元素不在当前位置
            swap(A[i], A[min]);  // 交换
    }
}

1.3 时间复杂度分析

方面	次数	说明
比较次数	n(n-1)/2	每趟比较 n-1-i 次，总 = (n-1)+(n-2)+…+1 = n(n-1)/2
移动次数	最好 0，最坏 3(n-1)	每趟最多交换一次（3次赋值）

关键特征：比较次数与初始序列无关！无论初始序列如何，比较次数恒为 n(n-1)/2。

情况	比较次数	移动次数	时间复杂度
最好	n(n-1)/2	0	O(n²)
最坏	n(n-1)/2	3(n-1)	O(n²)
平均	n(n-1)/2	3(n-1)/2	O(n²)

1.4 空间复杂度

O(1)，原地排序。

1.5 稳定性

不稳定。反例：序列 [5, 5, 3]，第 1 趟选最小值 3，与第 1 个 5 交换 → [3, 5, 5]，两个 5 的相对顺序改变了（原来第 1 个 5 到了后面）。

---

2. 堆排序（Heap Sort）

2.1 堆的定义

堆（Heap） 是一棵完全二叉树，满足：

• 大根堆（大顶堆）：每个结点的值 ≥ 其左右孩子的值，即 A[i] ≥ A[2i+1] 且 A[i] ≥ A[2i+2]
• 小根堆（小顶堆）：每个结点的值 ≤ 其左右孩子的值

堆排序使用大根堆进行升序排序。

2.2 基本思想

堆排序的核心思想是：

1. 建堆：将无序序列调整为大根堆
2. 排序：将堆顶（最大值）与堆的最后一个元素交换，堆的大小减 1，再对堆顶进行向下调整（sift down），恢复堆性质。重复此过程直到堆大小为 1。

2.3 向下调整算法（核心）

void SiftDown(ElementType A[], int k, int n) {
    // 对 A[k] 进行向下调整，堆的大小为 n
    // n 是堆中元素个数，不是数组总长
    ElementType temp = A[k];  // 暂存待调整的元素
    int i = k;
    int j = 2 * i + 1;  // j 指向 i 的左孩子
    while (j < n) {  // 存在左孩子
        // 选左右孩子中较大的一个
        if (j + 1 < n && A[j].key < A[j+1].key)
            j++;  // j 指向右孩子（较大的）
        // 如果孩子比父节点大，则上移
        if (A[j].key > temp.key) {
            A[i] = A[j];  // 孩子上移到父节点位置
            i = j;         // 继续向下调整
            j = 2 * i + 1;
        } else {
            break;  // 堆性质满足，停止调整
        }
    }
    A[i] = temp;  // 将暂存元素放到最终位置
}

2.4 建堆过程

void BuildMaxHeap(ElementType A[], int n) {
    // 从最后一个非叶子结点开始，依次向前进行向下调整
    // 最后一个非叶子结点的下标 = n/2 - 1（0-indexed）
    for (int i = n / 2 - 1; i >= 0; i--) {
        SiftDown(A, i, n);
    }
}

建堆时间复杂度：O(n)。证明如下：

• 第 i 层（从 0 开始）有 2^i 个结点，每个结点最多下调 h-i 次（h 为树高）
• 总代价 = ∑ᵢ₌₀ʰ 2^i · (h-i) = ∑ⱼ₌₀ʰ 2^(h-j) · j = 2^h · ∑ⱼ₌₀ʰ j/2^j ≤ 2^h · 2 = 2n = O(n)

2.5 堆排序完整算法

void HeapSort(ElementType A[], int n) {
    // 堆排序，A[0..n-1]
    BuildMaxHeap(A, n);  // 第1步：建大根堆，O(n)
    for (int i = n - 1; i > 0; i--) {
        swap(A[0], A[i]);  // 堆顶（最大值）与末尾交换
        SiftDown(A, 0, i);  // 对堆顶向下调整，堆大小减 1
    }
}

2.6 时间复杂度分析

阶段	时间复杂度	说明
建堆	O(n)	自底向上调整，线性时间
排序	O(n log n)	n-1 次调整，每次 O(log n)
总计	O(n log n)	最好/最坏/平均均为 O(n log n)

堆排序的时间复杂度与初始序列无关，始终为 O(n log n)。这是堆排序的重要优势。

调整次数详细分析：n-1 次 SiftDown 操作，第 i 次调整的树高为 ⌊log₂i⌋，总调整次数 ≈ ∑ᵢ₌₂ⁿ ⌊log₂i⌋ ≤ n log₂n。

2.7 空间复杂度

O(1)，原地排序（仅 SiftDown 中的 temp 变量）。

2.8 稳定性

不稳定。建堆和调整过程会打乱相同关键字的相对顺序。

---

3. 简单选择排序 vs 堆排序 对比表

对比维度	简单选择排序	堆排序
基本思想	线性扫描选最小	利用堆结构选最大
选最值效率	O(n)	O(log n)
比较次数	恒为 n(n-1)/2	O(n log n)
总时间复杂度	O(n²)	O(n log n)
空间复杂度	O(1)	O(1)
稳定性	不稳定	不稳定
适用场景	n 较小	大规模数据，需要稳定 O(n log n)

核心区别：简单选择排序每趟用 O(n) 时间选最值，堆排序用 O(log n) 时间维护堆来选最值。

---

三、记忆辅助

1. 简单选择 = 每趟选最小：像打擂台，每轮选出最弱的淘汰到前面
2. 堆排序 = 建堆 + 反复取堆顶：大根堆堆顶是最大值，取出来放末尾，再调整
3. 建堆 O(n) 不是 O(n log n)：自底向上建堆是线性的，这是常考点
4. 堆排序稳定性：不稳定！建堆过程中相同关键字的相对位置会改变
5. 下标公式（0-indexed）：父 i → 左孩子 2i+1，右孩子 2i+2；子 j → 父 ⌊(j-1)/2⌋

---

四、例题精解

例题 1：建堆过程模拟

题目：对序列 (4, 6, 8, 5, 9) 建立大根堆（0-indexed），写出建堆过程。

第一步：审题 使用自底向上的方法建大根堆。n=5，从最后一个非叶子结点（下标 5/2-1=1）开始调整。

第二步：逐过程模拟

初始完全二叉树：

        4
       / \
      6    8
     / \
    5   9

第 1 步：调整下标 1（值 6）

• 左孩子 5（下标 3），右孩子 9（下标 4）
• max(6, 5, 9) = 9，交换 6 和 9

        4
       / \
      9    8
     / \
    5   6

第 2 步：调整下标 0（值 4）

• 左孩子 9（下标 1），右孩子 8（下标 2）
• max(4, 9, 8) = 9，交换 4 和 9

        9
       / \
      4    8
     / \
    5   6

• 继续调整下标 1（值 4）：左孩子 5，右孩子 6
• max(4, 5, 6) = 6，交换 4 和 6

        9
       / \
      6    8
     / \
    5   4

第三步：解答 建堆结果（大根堆）：[9, 6, 8, 5, 4]

第四步：总结 建堆从最后一个非叶子结点开始，自底向上、自左向右依次调整。每个结点的调整是向下进行的，直到满足堆性质或到达叶子。

---

例题 2：堆排序完整过程

题目：对序列 (4, 6, 8, 5, 9) 进行堆排序，写出排序过程中每趟的结果。

第一步：审题 先建大根堆，然后反复取堆顶与末尾交换并调整。

第二步：逐趟模拟

建堆后：[9, 6, 8, 5, 4]

第 1 趟：交换 A[0]=9 和 A[4]=4 → [4, 6, 8, 5, 9]

• 对前 4 个元素调整：调整 4→8→4，得到 [8, 6, 4, 5, 9]

第 2 趟：交换 A[0]=8 和 A[3]=5 → [5, 6, 4, 8, 9]

• 对前 3 个元素调整：调整 5→6→5，得到 [6, 5, 4, 8, 9]

第 3 趟：交换 A[0]=6 和 A[2]=4 → [4, 5, 6, 8, 9]

• 对前 2 个元素调整：调整 4→5→4，得到 [5, 4, 6, 8, 9]

第 4 趟：交换 A[0]=5 和 A[1]=4 → [4, 5, 6, 8, 9]

第三步：解答 最终有序序列：[4, 5, 6, 8, 9]

第四步：总结 堆排序共需 n-1 趟，每趟交换后调整的树高为 ⌊log₂i⌋。总时间复杂度严格为 O(n log n)，与初始序列无关。

---

五、考情分析

年份	题型	考点	难度
高频	分析题	建堆过程模拟	★★★
高频	选择题	堆排序时间复杂度分析	★★☆
中频	选择题	简单选择排序的稳定性	★★☆
中频	应用题	在堆中插入/删除元素	★★★

命题趋势：

• 建堆过程的手工模拟是高频大题
• 堆排序时间复杂度的推导证明（特别是建堆的 O(n) 证明）偶有考查
• 简单选择排序常与堆排序对比出题

---

六、易错点

1. 建堆的起始位置：从最后一个非叶子结点开始，不是从最后一个叶子结点。0-indexed 下为 n/2-1
2. SiftDown 的方向：是向下调整（与孩子比较），不是向上调整。向上调整是插入堆的操作
3. 简单选择排序的稳定性：不稳定！不要因为"选最小"就觉得稳定
4. 堆排序的空间复杂度：O(1)，是原地排序。不要误以为需要额外数组
5. 建堆复杂度的证明：不是 O(n log n)，是 O(n)。关键在于各层结点数和调整深度的乘积求和
6. 下标计算：0-indexed 和 1-indexed 的公式不同，考试中需注意题目要求

---

七、来源标注

• 《数据结构（C语言版）》严蔚敏，第10.4节 选择排序
• 《数据结构》王道考研，第7章 7.4节 选择排序
• 408考试大纲：数据结构部分-选择排序与堆排序
• 《算法导论》Thomas H. Cormen，第6章 堆排序