8.4考研408简单选择排序与堆排序知识点深度解析

考研408「简单选择排序与堆排序」知识点全解析

一、简单选择排序

1.1 定义与核心思想

简单选择排序（Selection Sort）是一种选择排序算法，其核心思想是：

• 每趟选择：从待排序序列中选择最小（或最大）的元素，与当前位置的元素交换。
• 逐步构建有序序列：经过$n-1$趟选择，最终得到完全有序序列。

时间复杂度：

• 最好/最坏/平均情况均为$O(n^2)$。
  空间复杂度：$O(1)$（原地排序）。
  稳定性：不稳定（相同元素可能交换位置）。

1.2 算法实现与易错点

1.2.1 代码实现

C语言实现：

void selectSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

Python实现：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

1.2.2 易错点

1. 交换逻辑：需在内层循环结束后进行交换，避免重复交换。
2. 边界条件：内层循环应遍历i+1到n-1，否则可能漏选元素。
3. 稳定性：相同元素交换会破坏稳定性，需特别注意。

1.2.3 真题与模拟题

2023年408真题：

简单选择排序的最坏时间复杂度为（ ）。
A. $O(n)$
B. $O(n\log n)$
C. $O(n^2)$
D. $O(1)$
答案：C
解析：无论数据初始状态如何，比较次数始终为$\frac{n(n-1)}{2}$。

模拟题1：
题目：对数组[5, 3, 8, 6](@ref)进行简单选择排序，写出第三趟排序后的结果。
解答：

第一趟：3,5,8,6 → 比较3次  
第二趟：3,5,8,6 → 比较2次  
第三趟：3,5,6,8 → 比较1次  
最终结果：3,5,6,8  

二、堆排序

2.1 定义与核心思想

堆排序（Heap Sort）是一种树形选择排序算法，利用堆结构高效选择极值。其核心步骤为：

1. 建堆：将无序数组调整为堆结构（大根堆或小根堆）。
2. 调整堆：反复交换堆顶元素与末尾元素，并重新调整堆，最终得到有序序列。

时间复杂度：

• 建堆：$O(n)$
• 调整堆：$O(n\log n)$
• 总体：$O(n\log n)$。
  空间复杂度：$O(1)$（原地排序）。
  稳定性：不稳定（相同元素可能交换位置）。

2.2 堆排序的实现与难点

2.2.1 堆的结构与调整

堆的定义：

• 大根堆：任意节点的值均不大于其子节点（根节点为最大值）。
• 小根堆：任意节点的值均不小于其子节点（根节点为最小值）。

调整堆（Heapify）：
从根节点开始，向下调整以维持堆性质。关键步骤：

1. 比较左右子节点，找出较大（大根堆）或较小（小根堆）者。
2. 若根节点小于子节点，交换并递归调整子树。

代码示例：

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;
    
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

2.2.2 建堆过程

建堆需从最后一个非叶子节点开始，逐步向上调整。例如，数组长度为$n$，最后一个非叶子节点索引为$\lfloor \frac{n}{2}\rfloor -1$。

示例：
数组[49, 38, 65, 97, 76, 13, 27, 49](@ref)建堆过程：

1. 从索引3（元素97）开始调整，无需交换。
2. 索引2（元素65）调整为大根堆，子节点38和76均小于65，无需调整。
3. 索引1（元素38）调整为大根堆，子节点27和49均小于38，无需调整。
4. 索引0（元素49）调整为大根堆，子节点38和65中65较大，交换后继续调整。

2.2.3 真题与模拟题

2024年408真题：

堆排序中，构建初始堆时需从最后一个非叶子节点开始调整，其索引为（ ）。
A. $\lfloor n/2\rfloor$
B. $\lceil n/2\rceil$
C. $n-1$
D. $n$
答案：A
解析：最后一个非叶子节点索引为$\lfloor \frac{n}{2}\rfloor -1$，向上调整至根节点。

模拟题2：
题目：对数组[12, 36, 24, 85, 47, 30, 53, 91](@ref)进行堆排序，写出建堆后的结果。
解答：

建堆后的大根堆：91,85,53,36,47,30,24,12  

三、综合对比与优化策略

3.1 简单选择排序 vs 堆排序

3.2 堆排序的优化

1. 三数取中法：选择首、尾、中间元素的中值作为基准，减少最坏情况概率。
2. 小堆优化：对小数组（如长度<10）改用插入排序，减少递归开销。

四、真题与模拟题汇总

4.1 真题解析

2023年408算法题：

给定数组[3, 6, 8, 10, 1, 2, 1](@ref)，用堆排序算法写出第一趟调整后的堆结构。
答案：

调整后的大根堆：8,6,3,10,1,2,1  

2024年408选择题：

堆排序的比较次数与（ ）无关。
A. 元素排列顺序
B. 表长
C. 关键字类型
D. 基准元素选择
答案：D
解析：基准元素仅影响交换次数，不影响比较次数。

4.2 模拟题

模拟题3：
题目：设计简单选择排序算法，对数组[9, 7, 5, 11, 12, 2, 14](@ref)进行排序，并计算比较次数。
解答：

比较次数：15次  
最终结果：

模拟题4：
题目：对数组[5, 5, 5, 5, 5](@ref)进行堆排序，说明稳定性。
解答：

排序结果：
稳定性：不稳定（中间元素交换）

五、总结与建议

1. 简单选择排序：适用于小规模数据或教学演示，优化空间有限。
2. 堆排序：大规模数据首选，需掌握建堆和调整堆的细节。
3. 实战技巧：
   • 堆排序的heapify函数是高频考点，需理解递归调整过程。
   • 简单选择排序的交换次数优化可通过记录最小值位置实现。