🃏 排序算法

打扑克前要按大小理牌，考试后要把分数从高到低排出来。排序算法就是教电脑「把乱糟糟的一串数排整齐」的三种经典招数：冒泡、插入、选择，还要会比比谁更快。

考纲知识点：冒泡排序、插入排序、选择排序
时间复杂度、空间复杂度、算法稳定性
简单算法复杂度的估算，含多项式、指数复杂度

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 四级

(7)掌握排序算法的概念，了解内排序和外排序的概念及差别，理解排序算法的时间复杂度、空间复杂度、使用场景以及稳定性。
(8)掌握排序算法中的冒泡排序、插入排序、选择排序的算法思想、排序步骤及代码实现。
(9)简单算法复杂度的估算，含多项式、指数复杂度。

📚

先学一学

花 5 分钟读完下面 5 课，再去闯关就不慌啦

🔀 排序是什么 & 内排序、外排序

排序就是把一组数按从小到大（或从大到小）排整齐。比如把 5, 3, 8, 1 排成 1, 3, 5, 8。电脑排数和小朋友排队一样，办法不同快慢差别很大。

🏠 内排序 vs 外排序

· 内排序：数据不多，全部能搬进内存（电脑的临时工作台）里排，快！
· 外排序：数据太多，内存放不下，得分批从硬盘（大仓库）取出来排，慢得多。
四级考的冒泡、插入、选择都是内排序。

💡 口诀：放得下内存=内排序；放不下要借硬盘=外排序。

⚖️ 稳定性：相等的两个数，先后序保不保

如果两个数一样大（比如两个 3），排序后原本在前面的还排前面，这种算法就稳定；要是它俩可能换位，就不稳定。考试最常问：冒泡、插入稳定，选择不稳定。

💡 口诀：稳不稳看相等元素；冒泡、插入稳，选择爱乱动。

🫧 冒泡排序：大的像气泡一样浮到最后

冒泡排序的思路是：从头开始，把相邻两个数比一比，大的往后换。一趟走完，最大的数就像气泡一样「浮」到最后。再从头来一趟，第二大的浮到倒数第二……直到全部排好。

🧪 看过程：把 5, 3, 8, 1 排整齐

第 1 趟：3, 5, 1, 8（5 和 3 换、5 和 8 不用换、8 和 1 换）→ 最大 8 到末尾。
第 2 趟：3, 1, 5, 8 → 5 到位。
第 3 趟：1, 3, 5, 8 → 排好啦！

💡 口诀：相邻比一比，大的往后移；每一趟送走一个最大的。

💻 读代码：冒泡核心两行

看得懂就好，不用背：

for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);

每趟少比较一个已经浮到末尾的大数，所以内层是 n-1-i。

💡 口诀：冒泡两层循环；比较只在相邻，大的往后冒。

🃏 插入排序：像整理手里的扑克牌

打扑克摸到新牌时，你会把它插到手里已经排好序的牌堆的正确位置。插入排序就是这个动作：从左往右，把每个数往前插到它该待的地方，前面永远已经排好。

🧪 看过程：把 5, 3, 8, 1 排整齐

开始只看第 1 个数 [5]（已排好）。
拿 3 往前插：[3, 5]
拿 8 往前插，8 比 5 大，待原地：[3, 5, 8]
拿 1 往前插到最前：[1, 3, 5, 8] 排好啦！

💡 口诀：前面已经排好队；新数来了一路往前比，比它大就往后让。

🎯 选择排序：每趟挑出最小的放最前

🧪 看过程：把 5, 3, 8, 1 排整齐

第 1 趟在整队里找最小 1，和第一位 5 换：[1], 3, 8, 5
第 2 趟在剩下的 3,8,5 里找最小 3，不动：[1,3], 8, 5
第 3 趟找最小 5，和 8 换：[1,3,5], 8 排好啦！

💡 口诀：选择排序 = 每趟挑最小的，放到前面已排好的末尾。

🆚 三种排序大对比

· 冒泡：相邻比、大的往后冒；两层循环；稳定。
· 插入：像理扑克，新数往前插；稳定。
· 选择：每趟找最小放前面；因为可能把后面的相等数换到前面来，所以不稳定。
三者都需要两层循环，数据量变大时都偏慢（最坏大概 n² 次比较），但胜在思路简单、代码好写。

💡 口诀：冒泡邻换、插入理牌、选择挑小；稳不稳，冒泡插入稳、选择不稳。

⏱️ 时间复杂度：数一数做了几层循环

算法快不快，用时间复杂度描述：大概做多少次操作。简单估法就是数循环层数：

🔢 常见等级

· 只有 1 层 for，循环 n 次 → 大概 n 次，写 O(n)。
· 2 层 for 套起来，每层约 n 次 → 约 n×n 次，写 O(n²)（多项式）。冒泡、插入、选择都是 O(n²)。
· 3 层套起来 → 约 n³。
多项式就像一个数自己乘自己几次：n²、n³……

💡 口诀：几层循环 ≈ 几次方；一层 O(n)、两层 O(n²)、三层 O(n³)。

📈 别小看指数复杂度

还有一种更猛的：指数复杂度，比如每次翻倍：2、4、8、16、32……写 2ⁿ。n=10 时 2ⁿ=1024，n=30 时已经超过 10 亿，电脑也扛不住。考纲说「含多项式、指数复杂度」，就是让你会分等级：指数增长比任何多项式都快得多，数据一大就完蛋。

💡 口诀：多项式像自己乘自己几次，指数像翻倍再翻倍；指数一上天，谁都等不起。

🌟 行业实际：给 1000 万人排序

数据很少时，冒泡、插入、选择又简单又好写；但数据很多（比如给一亿人按成绩排序），工程师就会换更快的排序（像快速排序、归并排序，那是更高级别的内容）。选算法要看数据量和使用场景，这正是四级要学会的「分得清快慢」。

💡 口诀：数少用简单的，数大要挑快的；先会数复杂度，再谈选算法。

🎯

闯关小锦囊 · 考点提醒

排序：把一组数排整齐；数据放得下内存是内排序，放不下要借硬盘是外排序。
冒泡：相邻比，大的往后冒（每趟送走最大）；插入：像理扑克往前插；选择：每趟挑最小放前面。
稳定性：相等元素不换位就稳定——冒泡、插入稳定，选择不稳定。
三种排序都要两层循环，时间复杂度约为 O(n²)（多项式）。
复杂度数循环：一层 O(n)、两层 O(n²)、三层 O(n³)；指数 2ⁿ 增长最快，数据一大就跑不动。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。