第 39 章基础排序——冒泡、选择与插入

🏗️ 前情回顾：上一章你学会了用大 O 记号分析算法的快慢。O(n²) 是一种常见但不够快的复杂度，但别小看它——很多经典的入门排序算法就是 O(n²)。这一章，我们动手实现三种最基础、最直观的排序：冒泡、选择和插入。它们虽然慢，但代码简单、思路清晰，是理解排序思想的绝佳起点。

🎯 本章目标

学完这一章，你能：

手写实现冒泡排序、选择排序和插入排序
理解每种排序的"一句话核心思想"
分析三种 O(n²) 排序的时间复杂度和空间复杂度
理解"稳定性"的概念，并能判断一个排序是否稳定
知道每种排序在什么场景下更合适

📖 故事引入

想象你有一副完全乱掉的扑克牌，要从小到大排好。你会怎么做？

你的同类小明说："我每次都从第一张开始，相邻两张比较，大的往后挪。一趟下来，最大的就'冒'到最后面了。重复几次就排好了。"

小红说："我每次都找到最小的那张，把它放到最前面，然后在剩下的牌里继续找最小的。"

而你说："我一张一张摸牌，每摸一张就把它插到手里已经排好的正确位置。"

这三个人用的正是冒泡排序、选择排序和插入排序——三种最简单的排序算法，每种都只用了最朴素的比较和交换。

🧱 知识讲解

39.1 冒泡排序（Bubble Sort）

核心思想：每次比较相邻的两个元素，如果前面的比后面的大就交换。一趟从头走到尾，最大的元素就像气泡一样"浮"到最后面。重复 n-1 趟，全部排好。

过程（以数组 [5, 3, 8, 1] 为例）：

初始：  5  3  8  1
第1趟： 3  5  1 | 8    (5和3交换，5和8不换，8和1交换，8"冒"到底)
第2趟： 3  1 | 5  8    (3和1交换，3和5不换)
第3趟： 1 | 3  5  8    (1和3交换，排完)

C++ 实现（带优化提前终止）：

cpp

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {        // 需要 n-1 趟
        bool swapped = false;                 // 标记本趟是否交换
        for (int j = 0; j < n - 1 - i; j++) { // 每趟比较范围缩小
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;                  // ✅ 优化：没有交换说明已排好
    }
}

🎯 复杂度：最坏 O(n²)，最好 O(n)（已排好序时只需一趟）。空间 O(1)。稳定。

39.2 选择排序（Selection Sort）

核心思想：每一轮"选中"当前未排序部分的最小元素，把它放到已排序部分的末尾。

过程（以 [5, 3, 8, 1] 为例）：

初始：  5  3  8  1
第1轮： 1 | 3  8  5    (找到最小 1，与位置0的5交换)
第2轮： 1  3 | 8  5    (找到最小 3，已在位置1)
第3轮： 1  3  5 | 8    (找到最小 5，与位置2的8交换)

C++ 实现：

cpp

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;                        // 假设当前位置最小
        for (int j = i + 1; j < n; j++) {      // 在后面找真正的最小值
            if (a[j] < a[minIdx])
                minIdx = j;
        }
        swap(a[i], a[minIdx]);                 // 把最小值放到前面
    }
}

🎯 复杂度：无论最好最坏都是 O(n²)（总是要扫描剩余部分找最小）。空间 O(1)。不稳定（因为交换可能跳过相等的元素）。

39.3 插入排序（Insertion Sort）

核心思想：像打扑克牌一样，一张一张摸牌，每摸到一张新牌就把它插到手里已经排好的正确位置。

过程（以 [5, 3, 8, 1] 为例）：

初始：  5
摸 3：  3  5            (3 比 5 小，插到 5 前面)
摸 8：  3  5  8         (8 最大，放最后)
摸 1：  1  3  5  8      (1 比前面的都小，一路插到最前)

C++ 实现：

cpp

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {             // 摸第 i 张牌
        int key = a[i];                        // 这张牌的值
        int j = i - 1;
        while (j >= 0 && a[j] > key) {          // 比 key 大的往后挪
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                        // 插入正确位置
    }
}

🎯 复杂度：最坏 O(n²)（倒序时每张牌都要挪到头），最好 O(n)（已排好时每张只比较一次）。空间 O(1)。稳定。

39.4 三种排序对比

	冒泡	选择	插入
核心操作	相邻交换	选最小→放前面	后移→插入
最好时间	O(n)	O(n²)	O(n)
最坏时间	O(n²)	O(n²)	O(n²)
空间	O(1)	O(1)	O(1)
稳定性	✅ 稳定	❌ 不稳定	✅ 稳定
交换次数	最多 n²/2	最多 n-1	最多 n²/2

📊 选谁？
数据基本有序 → 插入排序最快，接近 O(n)
数据量很小（n ≤ 20）→ 三种都可以，插入通常最快
想交换次数最少 → 选择排序，每轮最多一次交换
初学理解 → 冒泡排序，最直观

39.5 什么是稳定性

稳定性：排序后，值相等的元素的相对顺序是否保持不变。

例如排序 [(3, A), (1, B), (3, C)]（按数值排）：

稳定排序：[(1, B), (3, A), (3, C)]——A 还是在 C 前面
不稳定排序：[(1, B), (3, C), (3, A)]——两个 3 的相对顺序可能变了

💡 稳定性什么时候重要？当你按多个关键字排序时。比如先按分数排，再按学号排——如果按学号排的排序不稳定，分数的顺序可能被打乱。不过，C++ 的 STL 提供了 stable_sort() 来解决这个问题（第 40 章会讲）。

✋ 动手试试

试试 1：用手动方式模拟冒泡排序。取 6 张扑克牌（或写 6 个数），一步步写出每趟的结果，直到排好。

试试 2：写完整程序，用三种排序分别对 {29, 10, 14, 37, 13} 排序，打印每轮结果，对比过程。

试试 3：生成一个倒序数组（5,4,3,2,1），分别用三种排序跑一遍，数一数比较次数和交换次数，看看哪个最少。

⚠️ 容易犯的错

错 1：冒泡排序的内层循环边界写错

❌ for (j = 0; j < n - 1; j++)——每次都比到最后一个，但后面已经是排好的了

✅ for (j = 0; j < n - 1 - i; j++)——每趟减少一位

错 2：选择排序的 minIdx 忘了更新

❌ 写了 swap(a[i], a[minIdx]) 但 minIdx 还是初始值，根本没去找真正的最小值

✅ 用 for (j = i+1; j < n; j++) 扫描并更新 minIdx

错 3：插入排序的 while 条件顺序写反

❌ while (a[j] > key && j >= 0)——先访问 a[j] 再检查 j，当 j 变成 -1 时访问数组越界！

✅ while (j >= 0 && a[j] > key)——先检查 j 是否有效（短路求值救命）

错 4：认为选择排序是稳定的

❌ 看到它找最小、放前面，觉得不会打乱顺序

✅ 反例：[5₁, 3, 5₂, 2] → 第一轮找最小 2，和 5₁ 交换 → [2, 3, 5₂, 5₁]，两个 5 的相对顺序变了！

📝 练习

基础题

1. 选择题

（1）冒泡排序最好情况的时间复杂度是：
A. O(n²) B. O(n) C. O(n log n) D. O(1)

（2）以下哪种排序是稳定的？
A. 选择排序 B. 冒泡排序 C. 以上都是 D. 以上都不是

（3）插入排序完成 n 个元素的排序，最坏需要多少次比较？
A. n B. n log n C. n² / 2 D. n³

2. 填空题

（1）冒泡排序每经过一趟，最大的元素会被放到 _____ 位置。

（2）选择排序每轮要做一件什么事？______________________________。

（3）三种 O(n²) 排序中，交换次数最少的是 _____ 排序。

提高题

3. 编程题 — 三种排序全家桶

输入第一行一个整数 n（1 ≤ n ≤ 1000），第二行 n 个整数。请分别用冒泡、选择、插入三种排序将它们升序排列，每排好一种就输出结果。你可以写三个函数 bubbleSort(), selectionSort(), insertionSort()。

4. 改进题 — 双向冒泡排序（鸡尾酒排序）

冒泡只向一个方向"冒"，其实可以来回冒：从左往右把最大的冒到右边，再从右往左把最小的冒到左边。这就是"鸡尾酒排序"（Cocktail Sort）。请尝试实现它，并分析它和普通冒泡相比有什么优势。

挑战题

5. 编程题 — 按个位数排序

输入 n 个数，用插入排序的方法，将它们按个位数从小到大排序。如果个位数相同，数值小的在前。你必须修改插入排序的比较逻辑，而不是先变换数据再排序。

（提示：比较两个数 a 和 b 时，先比较 a%10 和 b%10）

🧠 本章小结

冒泡排序：相邻比较，大的往后"冒"，优化：无交换则提前终止
选择排序：每轮选最小，放到前面，交换次数最少
插入排序：像理扑克牌，摸一张插一张，数据有序时极快

三种都是 O(n²)：适合 n ≤ 10⁴ 的小数据

稳定性：
  稳定 = 相等元素的相对顺序不变
  冒泡 ✅ | 选择 ❌ | 插入 ✅

📝 配套练习

共6题。三种排序各一题独立练+一题对比练。M6最强调"理解排序内部机制"的章节。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1116	https://hydro.ac/p/luogu-P1116	冒泡排序、交换计数=逆序对
◆ 拓展	luogu-P1059	https://hydro.ac/p/luogu-P1059	手写排序+去重
◆ 拓展	luogu-P1781	https://hydro.ac/p/luogu-P1781	选择排序、string比较
◆ 拓展	luogu-P1012	https://hydro.ac/p/luogu-P1012	自定义比较、排序模拟
◆ 拓展	无	—	手写插入排序+统计移位次数
◆ 拓展	无	—	对同一数组分别用三种排序，统计比较/交换次数

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 5 道◆拓展题，覆盖不同变式和细节。

配套练习

共6题。三种排序各一题独立练+一题对比练。M6最强调"理解排序内部机制"的章节。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1116	https://hydro.ac/p/luogu-P1116	冒泡排序、交换计数=逆序对
◆ 拓展	luogu-P1059	https://hydro.ac/p/luogu-P1059	手写排序+去重
◆ 拓展	luogu-P1781	https://hydro.ac/p/luogu-P1781	选择排序、string比较
◆ 拓展	luogu-P1012	https://hydro.ac/p/luogu-P1012	自定义比较、排序模拟
◆ 拓展	无	—	手写插入排序+统计移位次数
◆ 拓展	无	—	对同一数组分别用三种排序，统计比较/交换次数

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 5 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我能手写冒泡排序，并加上提前终止优化
[ ] 我能手写选择排序
[ ] 我能手写插入排序
[ ] 我知道三种排序的最好/最坏复杂度
[ ] 我能解释稳定性的含义，判断每种排序是否稳定
[ ] 我知道什么场景用哪种排序更合适

🚀 下章预告：手写 O(n²) 排序练完之后，你会发现——C++ 其实早给你准备了一把"万能排序刀"：sort() 函数，O(n log n)，一行代码搞定。下一章，我们走进 STL 的高级排序世界，学会用 sort() 和各种自定义比较。

第 39 章 基础排序——冒泡、选择与插入 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

39.1 冒泡排序（Bubble Sort） ​

39.2 选择排序（Selection Sort） ​

39.3 插入排序（Insertion Sort） ​

39.4 三种排序对比 ​

39.5 什么是稳定性 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：冒泡排序的内层循环边界写错 ​

错 2：选择排序的 minIdx 忘了更新 ​

错 3：插入排序的 while 条件顺序写反 ​

错 4：认为选择排序是稳定的 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​