DAY04-预习
2026-07-24 16:55:56
发布于：广东
82阅读
0回复
0点赞
🔥 C++ 三大排序算法 · 课前预习笔记
明天要学的是 “插入排序”、“桶排序”和“sort排序” ——三个超实用的排序方法！前两个让你理解排序的原理，第三个是 “神器” ，写代码时直接用，又快又方便！
一、先搞懂：插入排序 —— 像整理扑克牌一样
1. 核心思想
把当前元素插入到前面已经排好序的序列中的正确位置。
就像你打扑克牌时，每次抓一张新牌，就插到手牌中正确的位置。
2. 生活类比
你手里有
[3, 5, 8]三张牌（已经排好了），又摸到了一张4，你会怎么做？
一看4 < 5，所以插到3和5之间 →[3, 4, 5, 8]
3. 图解过程
初始：[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]
✅ 排好了！
4. 代码实现
#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;
}
5. 关键点
| 要点 | 说明 |
|---|---|
| 从第2个开始 | 第1个元素默认已经排好了 |
| 向前比较 | 从后往前找，比 key 大的都往后挪 |
| 插入位置 | j + 1 就是 key 的正确位置 |
| 时间复杂度 | O(n²)（最坏情况），O(n)（最好情况——已经有序） |
6. 特点总结
| 特点 | 说明 |
|---|---|
| ✅ 优点 | 数据基本有序时特别快（O(n)） |
| ❌ 缺点 | 数据乱序时是 O(n²)，慢 |
| 稳定性 | ✅ 稳定 |
| 适用场景 | 数据量小，或者数据基本有序 |
二、桶排序 —— 用“桶”来分类放
1. 核心思想
准备一排“桶”（数组），每个桶代表一个数字，出现一次就往对应桶里丢一个标记。
这种排序不是比较大小，而是统计每个数字出现了多少次，然后按顺序输出。
2. 生活类比
老师要统计全班同学的成绩分布（0~100分）：
- 准备101个盒子（0分到100分各一个）
- 每个同学考了多少分，就往对应的盒子里丢一颗豆子
- 最后从0分盒子到100分盒子，把豆子倒出来就知道分布了
3. 图解过程
原始数据：[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] ✅
4. 代码实现
#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;
}
5. 关键点
| 要点 | 说明 |
|---|---|
| 桶的个数 | 取决于数据的取值范围（比如数字 0~1000） |
| 计数 | bucket[x]++ 表示 x 出现了一次 |
| 输出 | 从小到大遍历桶，桶里有多少个就输出多少次 |
| 时间复杂度 | O(n + m)（n是数据个数，m是桶的个数） |
💡 桶排序是所有排序里最快的（O(n)级别），但有限制！
6. 桶排序的优缺点
| 特点 | 说明 |
|---|---|
| ✅ 优点 | 超级快！O(n) 级别，不依赖比较 |
| ❌ 缺点 | 需要知道数据范围，浪费内存（范围大了桶太多） |
| ❌ 缺点 | 只能排整数（不能排小数、字符串） |
| 适用场景 | 数据范围小且已知的整数（比如考试成绩 0~100） |
7. 桶排序的常见应用
// 应用1：统计年龄分布（0~120岁）
int age[121] = {0};
for (...) age[输入年龄]++;
// 应用2：统计考试成绩等级（A/B/C/D）
int level[4] = {0}; // 0:A, 1:B, 2:C, 3:D
for (...) level[等级]++;
三、sort 排序 —— C++ 自带的“神器”
1. 什么是 sort？
sort是 C++ 标准库里的排序函数，效率高、用起来方便，日常做题首选！
它内部用的是快速排序 + 其他优化，时间复杂度 O(n log n)，比冒泡、选择、插入快得多！
2. 需要头文件
#include <algorithm> // algorithm = 算法库
3. 基本语法
sort(起始地址, 结束地址);
// 注意：结束地址是最后一个元素的后一个位置！
4. 排序数组（从小到大）
#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;
}
5. 如果习惯用 a[1]~a[n]
// 如果你习惯下标从1开始，要这样写：
sort(a + 1, a + n + 1); // 从 a[1] 到 a[n] 排序
6. 从大到小排序（加第三个参数）
#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>());
// greater<int>() 表示"更大的放前面"
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
return 0;
}
7. 自定义排序规则（高级用法）
如果你想按自己的规则排序，可以自己写一个比较函数：
#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）
for (int i = 1; i <= 5; i++) {
cout << a[i] << " ";
}
return 0;
}
8. sort 的特点
| 特点 | 说明 |
|---|---|
| 时间复杂度 | O(n log n)，很快！ |
| 稳定性 | ❌ 不稳定（但一般不需要关心） |
| 适用场景 | 所有场景！能用就用！ |
💡 终极建议：日常做题 无脑用 sort！自己写排序算法是为了理解原理，真要干活的时候，
sort又快又省心。
四、三大排序对比总结
| 排序 | 时间复杂度（平均） | 稳定性 | 是否比较 | 额外内存 | 代码难度 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | ✅ 稳定 | ✅ 比较 | 不需要 | ⭐⭐ |
| 桶排序 | O(n+m) | ✅ 稳定 | ❌ 不比较 | 需要 | ⭐⭐ |
| sort | O(n log n) | ❌ 不稳定 | ✅ 比较 | 不需要 | ⭐ 最简单 |
怎么选？
| 场景 | 推荐 |
|---|---|
| 数据量小（n ≤ 1000） | 随便哪种都行 |
| 数据量大（n ≥ 10000） | 用 sort |
| 数据范围小且已知（如 0~100） | 桶排序最快 |
| 数据基本有序 | 插入排序很快 |
| 日常工作/竞赛 | 用 sort |
五、练习：用三种方式解决同一个问题
题目
输入 n 个整数（1 ≤ n ≤ 1000，每个数在 1~100 之间），按从小到大排序输出。
解法一：插入排序
// 手写插入排序
for (int i = 2; i <= n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 1 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
解法二：桶排序
// 因为数据范围是 1~100，用桶排序最快！
int bucket[105] = {0};
for (int i = 1; i <= n; i++) {
int x; cin >> x;
bucket[x]++;
}
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= bucket[i]; j++) {
cout << i << " ";
}
}
解法三：sort 排序（推荐！）
// 一行搞定！
sort(a + 1, a + n + 1);
📝 快速记忆卡
| 排序 | 一句话记忆 |
|---|---|
| 插入排序 | 新牌插入到已排好的牌里 |
| 桶排序 | 数字做桶下标，计数然后输出 |
| sort | 一行搞定，又快又方便！ |
🔥 预习小任务
- 插入排序中，如果数据已经是升序的，时间复杂度是多少？
- 桶排序中，如果数据范围是 0~1000000，要开多大的桶？有什么问题？
- 如果要对 100000 个数据进行排序，上面三种排序用哪个最合适？为什么？
明天上课带着这些问题来，效果翻倍！🚀
有帮助，赞一个