四级 - 排序与稳定性

作者： 作者的头像   huolong , 时间：2026-10-05 14:40:12 , 所有人可见, 阅读  7

GESP C++ 四级算法专项讲义：排序与稳定性

第一部分：核心概念与稳定性（Geps 理论题高频考点）

1. 什么是排序？

排序（Sorting）是指将一组无序的数据记录调整为有序（升序或降序）的序列。在 C++ 中，我们通常使用一维数组来存储待排序的数据。

2. 排序算法的稳定性（Stability）

  • 定义：如果待排序的序列中，存在多个关键字相同的记录：$R_i = R_j$，且在排序前 $R_i$ 在 $R_j$ 的前面；若使用某个排序算法排序后，$R_i$ 依然在 $R_j$ 的前面，则称这个排序算法是稳定的。反之，如果可能导致它们的相对位置发生颠倒，则称它是不稳定的。
  • GESP 考点结论（必须背熟）：
  • 稳定的排序算法：冒泡排序、插入排序、归并排序等。
  • 不稳定的排序算法：选择排序、快速排序、堆排序等。

第二部分：基础排序算法详解（C++ 代码实现）

1. 冒泡排序 (Bubble Sort)

  • 基本思想：重复地走访要排序的数列，比较相邻的两个元素。如果它们的顺序错误就把它们交换过来。每一轮会将当前未排序的最大（或最小）元素“冒泡”到顶端。
  • 时间复杂度：最坏/平均 $O(n^2)$，最好（已有序）$O(n)$。
  • 稳定性：稳定。

C++ 代码实现（升序）

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // 优化：记录是否发生过交换
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) { // 相邻元素比较
                // 交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // 如果这一轮没有交换，说明已经完全有序，提前退出
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

2. 插入排序 (Insertion Sort)

  • 基本思想：像打扑克牌摸牌一样，将数组分为“已排好序”和“未排序”两部分。每次从未排序部分取出一个元素，在已排序部分从后向前扫描，找到合适的位置插进去。
  • 时间复杂度：最坏/平均 $O(n^2)$，最好（已有序）$O(n)$。
  • 稳定性：稳定。

C++ 代码实现（升序）

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 当前需要插入的元素
        int j = i - 1;

        // 将已排序部分大于 key 的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 插入到正确位置
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

3. 选择排序 (Selection Sort)

  • 基本思想：每一轮在未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置，直到所有元素排完。
  • 时间复杂度：无论什么情况，时间复杂度都是固定的 $O(n^2)$。
  • 稳定性：不稳定。

C++ 代码实现（升序）

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 假设当前位置是最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值下标
            }
        }
        // 将找到的最小值与当前位置交换
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

第三部分：GESP 四级考点总结表

算法名称 稳定性 最优时间复杂度 最坏时间复杂度 空间复杂度 核心特征提示
冒泡排序 稳定 $O(n)$ $O(n^2)$ $O(1)$ 相邻比较，遇相等不交换
插入排序 稳定 $O(n)$ $O(n^2)$ $O(1)$ 类似摸牌，适合基本有序
选择排序 不稳定 $O(n^2)$ $O(n^2)$ $O(1)$ 每次找极值，跨越式交换

第四部分：GESP 风格课后练习题

一、 单选题

1. 下列关于排序算法稳定性的说法中，正确的是（ ） A. 冒泡排序是不稳定的排序算法
B. 插入排序是不稳定的排序算法
C. 选择排序是不稳定的排序算法
D. 以上算法全都不稳定

2. 对序列 [38, 27, 43, 3, 9, 82, 10] 进行从小到大的冒泡排序，第一轮冒泡结束后，数组的最后一个元素（即下标最大的元素）是（ ） A. 10
B. 38
C. 82
D. 9

3. 下列排序算法中，无论初始数据状况如何，其比较次数和时间复杂度都不会发生改变的是（ ） A. 冒泡排序
B. 插入排序
C. 选择排序
D. 快速排序

4. 有五个元素 (A, B, C, D, E) 具有相同的主关键字，它们在发生交换或移动时，以下哪个算法能保证它们原本的相对先后顺序不变？ A. 选择排序
B. 插入排序
C. 快速排序
D. 堆排序

二、 程序阅读/填空题

5. 阅读代码，回答输出结果：

#include <iostream>
using namespace std;

void solve(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int idx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[idx]) {
                idx = j;
            }
        }
        int t = a[i];
        a[i] = a[idx];
        a[idx] = t;
    }
}

int main() {
    int a[] = {5, 2, 8, 2, 1};
    solve(a, 5);
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

问题：程序运行后的最终输出结果是什么？

参考答案及解析

  1. 答案：C

  2. 解析：冒泡和插入是稳定的，选择排序是不稳定的，必须牢记。

  3. 答案：C

  4. 解析：冒泡排序每一轮会将当前范围内的最大值沉到最右侧。原数组的最大值是 82，因此第一轮结束后 82 会被换到最右侧。

  5. 答案：C

  6. 解析：选择排序无论数组原本是有序还是倒序，双重循环都要完整执行，比较次数固定为 $\frac{n(n-1)}{2}$，时间复杂度恒为 $O(n^2)$。

  7. 答案：B

  8. 解析：考察稳定性。四个选项中只有插入排序是稳定排序算法。

  9. 答案：1 2 2 5 8

  10. 解析：
    • 代码实现的是选择排序（升序）。
    • 原数组：{5, 2, 8, 2, 1}
    • 第 1 轮：找到全局最小的 1，与首位 5 交换 $\rightarrow$ {1, 2, 8, 2, 5}
    • 第 2 轮：在剩下的 {2, 8, 2, 5} 中找最小的 2（注意：若有多个相同最小值，根据代码 a[j] < a[idx]，会选择靠前的那个 2），与第二位 2 交换位置（位置没变） $\rightarrow$ {1, 2, 8, 2, 5}
    • 第 3 轮：在 {8, 2, 5} 中找最小的 2（即第二个 2），与第三位的 8 交换 $\rightarrow$ {1, 2, 2, 8, 5}
    • 第 4 轮：在 {8, 5} 中找最小的 5，与第四位的 8 交换 $\rightarrow$ {1, 2, 2, 5, 8}。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com