20260228 142212 Cpp 入门第十二课

第十二章：排序算法——让数据井然有序 ¶

你好！欢迎来到第十二章！在日常生活中，我们经常需要把东西排好序，比如按身高排队、按分数排名、按时间顺序排列照片。在计算机科学中，排序是最基础也最重要的算法之一。虽然C++的STL提供了强大的 sort 函数，但学习排序算法能帮助我们理解计算机如何工作，锻炼逻辑思维。这一章我们就来学习几种经典的排序算法，并亲手实现它们！

12.1 什么是排序算法？¶

排序就是将一组数据按照某种规则重新排列，比如从小到大（升序）或从大到小（降序）。

想象你有一堆乱序的扑克牌，你要把它们按数字从小到大整理好。你会怎么做？不同的方法对应不同的排序算法。

本章我们将学习：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序（进阶）
- 归并排序（进阶）

12.2 冒泡排序 ¶

12.2.1 算法思想 ¶

冒泡排序就像水中的气泡，轻的气泡会慢慢浮到上面。每次比较相邻的两个元素，如果顺序不对（比如前大后小），就交换它们。这样每一轮都会把最大的数“冒泡”到最后。

过程演示（升序）：
初始数组：[5, 3, 8, 1, 2]

第一轮：
- 比较5和3，5>3，交换 → [3, 5, 8, 1, 2]
- 比较5和8，5<8，不交换 → [3, 5, 8, 1, 2]
- 比较8和1，8>1，交换 → [3, 5, 1, 8, 2]
- 比较8和2，8>2，交换 → [3, 5, 1, 2, 8]（最大数8已就位）

第二轮：
- 比较3和5，3<5，不交换 → [3, 5, 1, 2, 8]
- 比较5和1，5>1，交换 → [3, 1, 5, 2, 8]
- 比较5和2，5>2，交换 → [3, 1, 2, 5, 8]（次大数5就位）

第三轮：
- 比较3和1，3>1，交换 → [1, 3, 2, 5, 8]
- 比较3和2，3>2，交换 → [1, 2, 3, 5, 8]（第三大3就位）

第四轮：
- 比较1和2，1<2，不交换 → 已完成

12.2.2 代码实现 ¶

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {          // 需要 n-1 轮
        for (int j = 0; j < n - 1 - i; j++) {  // 每轮比较次数减少
            if (arr[j] > arr[j + 1]) {          // 如果前大后小，交换
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 3, 8, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    cout << "排序后：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

12.2.3 优化 ¶

如果某一轮没有发生任何交换，说明数组已经有序，可以提前结束。

void bubbleSortOptimized(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;               // 标记是否交换
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);    // 可以用swap函数
                swapped = true;
            }
        }
        if (!swapped) break;                 // 没有交换，退出
    }
}

12.2.4 阶段性练习 ¶

练习1：用冒泡排序对数组 [9, 2, 5, 1, 7] 进行升序排序，写出每轮结果。
练习2：实现降序冒泡排序（从大到小）。
练习3：统计冒泡排序中交换的次数。

12.3 选择排序 ¶

12.3.1 算法思想 ¶

选择排序的思路很简单：每一轮从未排序的部分中找出最小的元素，放到已排序部分的末尾。

过程演示（升序）：
初始：[5, 3, 8, 1, 2]
- 第一轮：找到最小元素1，与第一个元素5交换 → [1, 3, 8, 5, 2]
- 第二轮：从剩余[3,8,5,2]中找到最小2，与第二个元素3交换 → [1, 2, 8, 5, 3]
- 第三轮：从剩余[8,5,3]中找到最小3，与第三个元素8交换 → [1, 2, 3, 5, 8]
- 第四轮：从剩余[5,8]中找到最小5，与第四个元素5（自身）不交换 → 完成

12.3.2 代码实现 ¶

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;
        }
    }
}

12.3.3 阶段性练习 ¶

练习1：用选择排序对数组 [8, 3, 6, 1, 4] 排序，写出每轮结果。
练习2：实现降序选择排序。
练习3：选择排序的交换次数最多是多少？

12.4 插入排序 ¶

12.4.1 算法思想 ¶

插入排序就像整理扑克牌：每次将一张牌插入到已经有序的手牌中的正确位置。

过程演示（升序）：
初始：[5, 3, 8, 1, 2]
- 第一张牌5，有序部分：[5]
- 取3，插入到5前面 → [3, 5, 8, 1, 2]
- 取8，比5大，位置不变 → [3, 5, 8, 1, 2]
- 取1，依次比较8、5、3，插入最前 → [1, 3, 5, 8, 2]
- 取2，依次比较8、5、3，插入3和1之间 → [1, 2, 3, 5, 8]

12.4.2 代码实现 ¶

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];           // 当前要插入的元素
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];    // 向后移动
            j--;
        }
        arr[j + 1] = key;           // 插入正确位置
    }
}

12.4.3 阶段性练习 ¶

练习1：用插入排序对 [7, 2, 5, 1, 9] 排序，写出每一步后数组的变化。
练习2：实现降序插入排序。
练习3：插入排序在什么情况下最快？什么情况下最慢？

int partition(int arr[], int low, int high) {
    int pivot = arr[low];          // 选第一个为基准
    int i = low, j = high;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--; // 从右找小于pivot的
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] <= pivot) i++; // 从左找大于pivot的
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;                // 基准归位
    return i;                      // 返回基准位置
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

调用时：quickSort(arr, 0, n-1);

12.5.3 阶段性练习 ¶

练习1：模拟快速排序对 [4, 7, 2, 1, 5, 3] 的过程。
练习2：尝试以中间元素为基准实现快速排序。

12.6 排序算法的比较 ¶

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(1)	稳定
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定

稳定性：如果两个相等的元素在排序前后的相对位置不变，则排序算法是稳定的。

12.7 编程实例讲解 ¶

实例1：成绩排序 ¶

题目：输入n个学生的姓名和成绩，按成绩从高到低排序，如果成绩相同则按姓名字典序排序。

#include <iostream>
#include <string>
#include <algorithm>  // 用sort，但我们可以手写排序
using namespace std;

struct Student {
    string name;
    int score;
};

// 冒泡排序（按成绩降序，成绩相同按姓名升序）
void sortStudents(Student stu[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (stu[j].score < stu[j + 1].score || 
                (stu[j].score == stu[j + 1].score && stu[j].name > stu[j + 1].name)) {
                swap(stu[j], stu[j + 1]);
            }
        }
    }
}

int main() {
    int n;
    cout << "请输入学生人数：";
    cin >> n;
    Student stu[100];
    for (int i = 0; i < n; i++) {
        cin >> stu[i].name >> stu[i].score;
    }
    sortStudents(stu, n);
    cout << "\n排序结果：" << endl;
    for (int i = 0; i < n; i++) {
        cout << stu[i].name << " " << stu[i].score << endl;
    }
    return 0;
}

实例2：排序算法效率对比 ¶

用随机数生成大量数据，测试不同排序算法的时间。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

// 冒泡排序、选择排序、插入排序、快速排序函数声明...

int main() {
    const int N = 10000;
    int arr1[N], arr2[N], arr3[N], arr4[N];
    srand(time(0));
    for (int i = 0; i < N; i++) {
        int val = rand() % 10000;
        arr1[i] = arr2[i] = arr3[i] = arr4[i] = val;
    }

    clock_t start, end;

    start = clock();
    bubbleSort(arr1, N);
    end = clock();
    cout << "冒泡排序时间：" << double(end - start) / CLOCKS_PER_SEC << "秒" << endl;

    // 测试其他排序...
    return 0;
}