🔥 C++ 三大排序算法 · 课前预习笔记
> 明天要学的是 “插入排序”、“桶排序”和“sort排序” ——三个超实用的排序方法！前两个让你理解排序的原理，第三个是 “神器” ，写代码时直接用，又快又方便！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、先搞懂：插入排序 —— 像整理扑克牌一样
1. 核心思想
> 把当前元素插入到前面已经排好序的序列中的正确位置。
就像你打扑克牌时，每次抓一张新牌，就插到手牌中正确的位置。
2. 生活类比
> 你手里有 [3, 5, 8] 三张牌（已经排好了），又摸到了一张 4，你会怎么做？
> 一看 4 < 5，所以插到 3 和 5 之间 → [3, 4, 5, 8]
3. 图解过程
4. 代码实现
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. 图解过程
4. 代码实现
5. 关键点
要点 说明 桶的个数 取决于数据的取值范围（比如数字 0~1000） 计数 bucket[x]++ 表示 x 出现了一次 输出 从小到大遍历桶，桶里有多少个就输出多少次 时间复杂度 O(n + m)（n是数据个数，m是桶的个数）
> 💡 桶排序是所有排序里最快的（O(n)级别），但有限制！
6. 桶排序的优缺点
特点 说明 ✅ 优点 超级快！O(n) 级别，不依赖比较 ❌ 缺点 需要知道数据范围，浪费内存（范围大了桶太多） ❌ 缺点 只能排整数（不能排小数、字符串） 适用场景 数据范围小且已知的整数（比如考试成绩 0~100）
7. 桶排序的常见应用
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、SORT 排序 —— C++ 自带的“神器”
1. 什么是 SORT？
> sort 是 C++ 标准库里的排序函数，效率高、用起来方便，日常做题首选！
它内部用的是快速排序 + 其他优化，时间复杂度 O(n log n)，比冒泡、选择、插入快得多！
2. 需要头文件
3. 基本语法
4. 排序数组（从小到大）
5. 如果习惯用 A[1]~A[N]
6. 从大到小排序（加第三个参数）
7. 自定义排序规则（高级用法）
如果你想按自己的规则排序，可以自己写一个比较函数：
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 之间），按从小到大排序输出。
解法一：插入排序
解法二：桶排序
解法三：SORT 排序（推荐！）
📝 快速记忆卡
排序 一句话记忆 插入排序 新牌插入到已排好的牌里 桶排序 数字做桶下标，计数然后输出 sort 一行搞定，又快又方便！
🔥 预习小任务
1. 插入排序中，如果数据已经是升序的，时间复杂度是多少？
2. 桶排序中，如果数据范围是 0~1000000，要开多大的桶？有什么问题？
3. 如果要对 100000 个数据进行排序，上面三种排序用哪个最合适？为什么？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
明天上课带着这些问题来，效果翻倍！🚀
