DAY8-预习
2026-07-18 20:44:28
发布于：广东
49阅读
0回复
0点赞
🔥 C++ 五大排序算法 · 课前预习笔记
明天要学的东西叫 “排序” ——就是把一堆乱七八糟的数据按顺序排好，比如考试成绩从高到低排名，或者把一串数字从小到大排好。排序是编程里最最最常用的技能之一！
一、先搞懂：排序是啥？有啥用？
生活类比
你有一副乱序的扑克牌：
5, 2, 8, 1, 9，想把它排成1, 2, 5, 8, 9。
排序就是把数据按一定规则重新排列（从小到大 / 从大到小）。
为什么需要排序？
| 场景 | 没排序 | 排好序 |
|---|---|---|
| 找最大值/最小值 | 要遍历一遍 | 直接取第一个/最后一个 |
| 找中位数 | 很麻烦 | 直接取中间位置 |
| 查成绩排名 | 不知道第几名 | 一看就知道 |
| 二分查找 | 用不了 | 嗖嗖快 |
💡 记住：排序让数据变得有秩序，后续操作会方便很多！
二、冒泡排序（Bubble Sort）—— 像气泡一样往上冒
1. 核心思想
相邻两个数比较，大的往后“冒”，就像水里的气泡一样，大的气泡慢慢浮到水面。
每一轮会把当前未排序部分的最大值“冒泡”到最后面。
2. 图解过程
第一轮：
[5, 2, 8, 1, 9]
↑ ↑
5>2 → 交换 → [2, 5, 8, 1, 9]
↑ ↑
5<8 → 不动 → [2, 5, 8, 1, 9]
↑ ↑
8>1 → 交换 → [2, 5, 1, 8, 9]
↑ ↑
8<9 → 不动 → [2, 5, 1, 8, 9]
✅ 最大值 9 冒到最后了！
第二轮：对 [2, 5, 1, 8] 继续冒泡
[2, 5, 1, 8, 9]
↑ ↑
2<5 → 不动
↑ ↑
5>1 → 交换 → [2, 1, 5, 8, 9]
↑ ↑
5<8 → 不动
✅ 8 冒到倒数第二了！
第三轮：对 [2, 1, 5] 继续
[2, 1, 5, 8, 9]
↑ ↑
2>1 → 交换 → [1, 2, 5, 8, 9]
↑ ↑
2<5 → 不动
✅ 5 冒到倒数第三了！
第四轮：对 [1, 2] 继续
[1, 2, 5, 8, 9]
↑ ↑
1<2 → 不动
✅ 全部排好了！
3. 代码实现
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 1; i <= n; i++) cin >> a[i];
// 冒泡排序（从小到大）
for (int i = 1; i <= n - 1; i++) { // 外层：需要 n-1 轮
for (int j = 1; j <= n - i; j++) { // 内层：每轮比较次数减少
if (a[j] > a[j + 1]) { // 相邻比较，大的往后
swap(a[j], a[j + 1]); // 交换
}
}
}
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
4. 关键点
| 要点 | 说明 |
|---|---|
外层循环 i |
表示第几轮，需要 n-1 轮 |
内层循环 j |
每轮比较 n-i 次（因为后面已经排好了） |
| 交换条件 | a[j] > a[j+1] → 大的往后冒 |
| 时间复杂度 | O(n²)（慢，数据多了不行） |
5. 优化版（加标记）
for (int i = 1; i <= n - 1; i++) {
bool swapped = false; // 标记本轮是否交换过
for (int j = 1; j <= n - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // 没交换说明已经排好了，提前结束
}
💡 如果某一轮没有发生任何交换，说明已经有序了，可以提前结束。
6. 特点总结
| 特点 | 说明 |
|---|---|
| ✅ 优点 | 代码简单，容易理解 |
| ❌ 缺点 | 太慢了，数据多的时候不实用 |
| 稳定性 | ✅ 稳定（相等元素不交换，顺序不变） |
| 适用场景 | 初学者入门，数据量小（n ≤ 1000） |
三、选择排序（Selection Sort）—— 每次选最小的
1. 核心思想
每一轮在未排序部分选最小的，放到最前面。
就像你在打扑克牌时，每次从手牌里找出最小的那张放最前面。
2. 图解过程
初始：[5, 2, 8, 1, 9]
第1轮：在 [5,2,8,1,9] 中找最小值 → 1
把 1 和 5 交换 → [1, 2, 8, 5, 9]
✅ 1 归位！
第2轮：在 [2,8,5,9] 中找最小值 → 2
已经在最前面，不动 → [1, 2, 8, 5, 9]
✅ 2 归位！
第3轮：在 [8,5,9] 中找最小值 → 5
把 5 和 8 交换 → [1, 2, 5, 8, 9]
✅ 5 归位！
第4轮：在 [8,9] 中找最小值 → 8
已经在最前面，不动 → [1, 2, 5, 8, 9]
✅ 全部排好了！
3. 代码实现
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 1; i <= n; i++) cin >> a[i];
// 选择排序（从小到大）
for (int i = 1; i <= n - 1; i++) {
int minPos = i; // 先假设第 i 个是最小值
for (int j = i + 1; j <= n; j++) { // 在后面找更小的
if (a[j] < a[minPos]) {
minPos = j; // 找到更小的，记录位置
}
}
if (minPos != i) {
swap(a[i], a[minPos]); // 把最小值放到前面
}
}
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
4. 关键点
| 要点 | 说明 |
|---|---|
外层循环 i |
表示放第 i 个位置（从第1个到第 n-1 个） |
内层循环 j |
在 i+1 到 n 中找最小值的位置 |
| 交换 | 把最小值和第 i 个位置交换 |
| 时间复杂度 | O(n²)（还是慢） |
5. 特点总结
| 特点 | 说明 |
|---|---|
| ✅ 优点 | 代码简单，交换次数少（最多 n-1 次） |
| ❌ 缺点 | 还是 O(n²)，数据多了慢 |
| 稳定性 | ❌ 不稳定（相等元素可能改变顺序） |
| 适用场景 | 数据量小，交换操作代价高的场景 |
四、插入排序（Insertion Sort）—— 像整理扑克牌
1. 核心思想
把当前元素插入到前面已经排好序的序列中的正确位置。
就像你打扑克牌时，每次抓一张新牌，就插到手牌中正确的位置。
2. 图解过程
初始：[5, 2, 8, 1, 9]
第1步：拿 2，插入到 [5] 中 → [2, 5, 8, 1, 9]
第2步：拿 8，插入到 [2,5] 中 → 8 比 5 大，放后面 → [2, 5, 8, 1, 9]
第3步：拿 1，插入到 [2,5,8] 中 → 1 最小，插最前面 → [1, 2, 5, 8, 9]
第4步：拿 9，插入到 [1,2,5,8] 中 → 9 最大，放最后 → [1, 2, 5, 8, 9]
✅ 排好了！
3. 代码实现
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 1; i <= n; i++) cin >> a[i];
// 插入排序（从小到大）
for (int i = 2; i <= n; i++) { // 从第2个开始，逐个插入
int key = a[i]; // 当前要插入的元素
int j = i - 1;
while (j >= 1 && a[j] > key) { // 把比 key 大的都往后移
a[j + 1] = a[j];
j--;
}
a[j + 1] = key; // 插入到正确位置
}
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
4. 关键点
| 要点 | 说明 |
|---|---|
| 从第2个开始 | 第1个元素默认已经排好了 |
| 向前比较 | 从后往前找，比 key 大的都往后挪 |
| 插入位置 | j + 1 就是 key 的正确位置 |
| 时间复杂度 | O(n²)（最坏情况），O(n)（最好情况） |
5. 特点总结
| 特点 | 说明 |
|---|---|
| ✅ 优点 | 数据基本有序时特别快（O(n)） |
| ❌ 缺点 | 数据乱序时还是 O(n²) |
| 稳定性 | ✅ 稳定 |
| 适用场景 | 数据量小，或者数据基本有序 |
五、桶排序（Bucket Sort）—— 用“桶”来分类放
1. 核心思想
准备一排“桶”（数组），每个桶代表一个数字，出现一次就往对应桶里丢一个标记。
这种排序不是比较大小，而是统计每个数字出现了多少次，然后按顺序输出。
2. 图解过程
原始数据：[5, 2, 8, 5, 2, 1, 9, 2]
步骤1：准备桶（假设数字范围是 1~10）
桶： [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
下标: 1 2 3 4 5 6 7 8 9 10
步骤2：遍历数据，往桶里加标记
遇到 5 → 桶[5]++
遇到 2 → 桶[2]++
遇到 8 → 桶[8]++
遇到 5 → 桶[5]++
遇到 2 → 桶[2]++
遇到 1 → 桶[1]++
遇到 9 → 桶[9]++
遇到 2 → 桶[2]++
最终桶：
桶： [1, 3, 0, 0, 2, 0, 0, 1, 1, 0]
下标: 1 2 3 4 5 6 7 8 9 10
步骤3：按顺序输出
1出现1次 → 输出 1
2出现3次 → 输出 2 2 2
5出现2次 → 输出 5 5
8出现1次 → 输出 8
9出现1次 → 输出 9
结果：[1, 2, 2, 2, 5, 5, 8, 9] ✅
3. 代码实现
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// 前提：知道数据的范围（比如 0~1000）
int bucket[1005] = {0}; // 准备桶，全部初始化为0
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
bucket[x]++; // 对应的桶计数+1
}
// 按顺序输出
for (int i = 0; i <= 1000; i++) { // 遍历每个桶
for (int j = 1; j <= bucket[i]; j++) { // 桶里有几个就输出几次
cout << i << " ";
}
}
return 0;
}
4. 关键点
| 要点 | 说明 |
|---|---|
| 桶的个数 | 取决于数据的取值范围（比如数字 0~1000） |
| 计数 | bucket[x]++ 表示 x 出现了一次 |
| 输出 | 从小到大遍历桶，桶里有多少个就输出多少次 |
| 时间复杂度 | O(n + m)（n是数据个数，m是桶的个数） |
💡 桶排序是所有排序里最快的（O(n)级别），但有限制！
5. 桶排序的优缺点
| 特点 | 说明 |
|---|---|
| ✅ 优点 | 超级快！O(n) 级别，不依赖比较 |
| ❌ 缺点 | 需要知道数据范围，浪费内存（范围大了桶太多） |
| ❌ 缺点 | 只能排整数（不能排小数、字符串） |
| 适用场景 | 数据范围小且已知的整数（比如考试成绩 0~100） |
六、sort 排序 —— C++ 自带的“神器”
1. 什么是 sort？
sort是 C++ 标准库里的排序函数，效率高、用起来方便，日常做题首选！
它内部用的是快速排序 + 其他优化，时间复杂度 O(n log n)，比冒泡、选择、插入快得多！
2. 怎么用 sort？
需要头文件：
#include <algorithm> // algorithm = 算法库
基本语法：
sort(起始地址, 结束地址);
// 注意：结束地址是最后一个元素的后一个位置！
3. 排序数组（从小到大）
#include <iostream>
#include <algorithm> // 别忘了！
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 0; i < n; i++) { // 注意：sort 默认从0开始！
cin >> a[i];
}
sort(a, a + n); // 排序！a 是起始地址，a+n 是结束地址
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
⚠️ 注意：
sort默认下标从 0 开始！如果你习惯用a[1]~a[n]，要这样写：sort(a + 1, a + n + 1); // 从 a[1] 到 a[n] 排序
4. 从大到小排序（加第三个参数）
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 1; i <= n; i++) cin >> a[i];
// 从大到小排序
sort(a + 1, a + n + 1, greater<int>());
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
5. 自定义排序规则（高级用法）
如果你想按自己的规则排序，可以自己写一个比较函数：
#include <iostream>
#include <algorithm>
using namespace std;
// 自定义比较函数：按个位数从小到大排
bool cmp(int x, int y) {
return x % 10 < y % 10; // 个位数小的排前面
}
int main() {
int a[6] = {0, 15, 23, 8, 42, 11}; // a[1]~a[5]
sort(a + 1, a + 6, cmp); // 按个位数排序
// 结果：11, 42, 23, 15, 8（个位数分别是 1,2,3,5,8）
return 0;
}
6. sort 的特点
| 特点 | 说明 |
|---|---|
| 时间复杂度 | O(n log n)，很快！ |
| 稳定性 | ❌ 不稳定（但一般不需要关心） |
| 适用场景 | 所有场景！能用就用！ |
七、五种排序对比总结
| 排序 | 速度（平均） | 速度（最坏） | 是否稳定 | 是否需要额外数组 | 代码难度 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | ✅ 稳定 | ❌ 不需要 | ⭐ 最简单 |
| 选择排序 | O(n²) | O(n²) | ❌ 不稳定 | ❌ 不需要 | ⭐ 简单 |
| 插入排序 | O(n²) | O(n²) | ✅ 稳定 | ❌ 不需要 | ⭐⭐ 较简单 |
| 桶排序 | O(n+m) | O(n+m) | ✅ 稳定 | ✅ 需要 | ⭐⭐ 较简单 |
| sort | O(n log n) | O(n log n) | ❌ 不稳定 | ❌ 不需要 | ⭐ 最简单 |
💡 终极建议：日常做题 无脑用 sort！自己写排序算法是为了理解原理，真要干活的时候，
sort又快又省心。
📝 快速记忆卡
| 排序 | 一句话记忆 |
|---|---|
| 冒泡排序 | 相邻比较，大的往后冒 |
| 选择排序 | 每次选最小的放前面 |
| 插入排序 | 新牌插入到已排好的牌里 |
| 桶排序 | 数字做桶下标，计数然后输出 |
| sort | 一行搞定，最快最方便！ |
🔥 预习小任务
- 冒泡排序中，为什么内层循环是
j <= n - i？ - 选择排序和冒泡排序，哪个交换次数更少？
- 如果要对 100000 个数据进行排序，上面哪种排序最合适？
sort(a + 1, a + n + 1)中，为什么结束地址是a + n + 1而不是a + n？
明天上课带着这些问题来，效果翻倍！🚀
有帮助，赞一个