程序设计考试总结

1.排序（冒泡算法）

冒泡排序是一种简单直观的排序算法，核心思想是通过重复遍历待排序序列，每次比较相邻的两个元素，若顺序错误则交换它们的位置，直到没有元素需要交换，排序完成。因其每轮会将最大（或最小）的元素 “浮” 到序列末端，类似气泡上升，故得名 “冒泡排序”。

一、核心原理

  1. 比较与交换：从序列起始位置开始，依次比较相邻的两个元素，若前一个元素大于后一个元素（升序排序），则交换两者位置。
  2. 一轮 “冒泡”：每完成一轮遍历，当前序列中最大的元素会被 “推” 到序列的末尾（无需再参与后续比较）。
  3. 重复执行：减少待排序序列的长度（排除已 “冒泡” 到末尾的元素），重复上述过程，直到整个序列有序。

二、排序步骤（以升序为例）

假设有待排序数组 [3, 1, 4, 1, 5, 9, 2, 6]，步骤如下：

  • 第 1 轮：比较所有相邻元素，将最大元素 9 “浮” 到末尾，数组变为 [1, 3, 1, 4, 2, 5, 6, 9]（最后一个元素 9 已确定）。
  • 第 2 轮：比较前 7 个元素，将次大元素 6 “浮” 到第 7 位，数组变为 [1, 1, 3, 2, 4, 5, 6, 9]（倒数第二个元素 6 已确定）。
  • 后续轮次：依次减少待排序长度，直到第 7 轮结束，数组完全有序。

三、C++ 实现（基础版与优化版）

1. 基础版实现

#include <iostream>
#include <vector>
using namespace std;

// 冒泡排序（升序）
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    // 外层循环：控制需要冒泡的轮数（n个元素需要n-1轮）
    for (int i = 0; i < n - 1; i++) {
        // 内层循环：每轮比较相邻元素，已确定的元素无需再比较
        // 第i轮后，末尾i个元素已有序，故只需比较到n-1-i
        for (int j = 0; j < n - 1 - i; j++) {
            // 若前一个元素大于后一个，交换位置
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); // C++标准库的交换函数
            }
        }
    }
}

// 测试
int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
    bubbleSort(arr);
    
    cout << "排序后：";
    for (int num : arr) {
        cout << num << " ";
    }
    // 输出：1 1 2 3 4 5 6 9 
    return 0;
}

2. 优化版实现（提前终止）

基础版的问题：若某一轮遍历中没有发生任何交换，说明数组已完全有序，可提前结束排序（无需继续后续轮次）。优化思路：增加一个标志位 isSwapped，记录当前轮是否发生交换，若未交换则直接退出循环。

void optimizedBubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool isSwapped; // 标志位：记录本轮是否发生交换
    
    for (int i = 0; i < n - 1; i++) {
        isSwapped = false; // 初始化：假设本轮无交换
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                isSwapped = true; // 发生交换，更新标志位
            }
        }
        // 若本轮无交换，说明数组已有序，直接退出
        if (!isSwapped) {
            break;
        }
    }
}

四、算法分析

  • 时间复杂度：
    • 最坏情况（完全逆序）：需要 n-1 轮，每轮比较 n-1, n-2, ..., 1 次，总操作次数为 n(n-1)/2，故复杂度为 O(n²)。
    • 最好情况（已完全有序）：优化版只需 1 轮遍历（无交换），复杂度为 O(n)。
  • 空间复杂度：仅使用常数级额外空间（标志位等），故为 O(1)（原地排序）。
  • 稳定性：稳定排序（相等元素不会交换位置，相对顺序保持不变）。

五、特点总结

  • 优点：实现简单，逻辑直观，适合小规模数据排序。
  • 缺点：效率较低（时间复杂度 O (n²)），不适合大规模数据。

冒泡排序是入门级排序算法，其核心思想（相邻元素比较交换）是理解更复杂排序算法的基础。

image-20251103124628973

2.排序（algorithm库）

一、先说明：using namespace std; 的作用

在代码开头添加 using namespace std; 后，无需再在标准库组件（如 cout、vector、sort 等）前加 std::，代码更简洁。

二、核心排序函数：sort（通用排序）

1. 头文件与基本用法

需包含 <algorithm> 头文件，支持对数组、vector、array 等容器排序。

#include <iostream>
#include <vector>
#include <algorithm> // 包含 sort 函数
using namespace std; // 简化命名空间

int main() {
    // 1. 对 vector 排序（默认升序）
    vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    sort(vec.begin(), vec.end()); // 排序范围：[begin, end)（左闭右开）
    cout << "升序排序后：";
    for (int num : vec) {
        cout << num << " "; // 输出：1 1 2 3 4 5 6 9
    }
    cout << endl;

    // 2. 对原生数组排序（降序）
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    // 用 greater<int>() 实现降序（需包含 <functional> 头文件，通常已间接包含）
    sort(arr, arr + n, greater<int>()); 
    cout << "降序排序后：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "; // 输出：9 6 5 5 2 1
    }
    cout << endl;

    // 3. 自定义排序规则（例如：按字符串长度排序）
    vector<string> strs = {"apple", "banana", "pear", "grape"};
    // 用 lambda 表达式定义比较规则：按长度从小到大
    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a.size() < b.size();
    });
    cout << "按长度排序后：";
    for (const auto& s : strs) {
        cout << s << " "; // 输出：pear apple grape banana
    }

    return 0;
}

2. 核心特性

  • 适用容器：支持所有提供 “随机访问迭代器” 的容器（vector、array、原生数组等）。
  • 排序规则：默认按 operator< 升序；可通过函数 / 仿函数 /lambda 自定义规则。
  • 时间效率：平均 O(nlogn)，远优于冒泡排序的 O(n²)。
  • 稳定性：不稳定（相等元素的相对顺序可能改变）。

三、稳定排序：stable_sort

如果需要保留相等元素的原始顺序（稳定排序），用 stable_sort。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Student {
    string name;
    int score;
};

int main() {
    vector<Student> students = {
        {"Alice", 80},
        {"Bob", 70},
        {"Charlie", 80}, // 与 Alice 成绩相同
        {"David", 70}    // 与 Bob 成绩相同
    };

    // 按成绩升序稳定排序（相等成绩的学生保留原始顺序）
    stable_sort(students.begin(), students.end(), 
        [](const Student& a, const Student& b) {
            return a.score < b.score;
        });

    cout << "按成绩稳定排序后：\n";
    for (const auto& s : students) {
        cout << s.name << " (" << s.score << ")\n";
    }
    // 输出（成绩相同的学生顺序与原始一致）：
    // Bob (70)
    // David (70)
    // Alice (80)
    // Charlie (80)

    return 0;
}

特性

  • 稳定性：保证相等元素的相对顺序与原始序列一致。
  • 效率：时间复杂度 O(nlogn)，空间复杂度略高于 sort（可能需要 O(n) 额外空间）。

四、与冒泡排序的对比

特性 冒泡排序 sort / stable_sort
实现难度 需手动写循环和交换 直接调用库函数，无需手动实现
时间复杂度 O(n²)（低效） O(nlogn)（高效）
适用场景 小规模数据、教学 实际开发（各种规模数据）
稳定性 可实现稳定 sort 不稳定，stable_sort 稳定
灵活性 需手动修改规则 支持自定义比较器（灵活）

总结

C++ 标准库的 sort 和 stable_sort 是实际开发的首选，无需重复造轮子（如手动实现冒泡排序）。通过 using namespace std; 可简化代码，让排序逻辑更清晰。仅在理解排序原理时，冒泡排序才有学习价值。