🔥 C++ 五大排序算法 · 课前预习笔记
> 明天要学的东西叫 “排序” ——就是把一堆乱七八糟的数据按顺序排好，比如考试成绩从高到低排名，或者把一串数字从小到大排好。排序是编程里最最最常用的技能之一！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、先搞懂：排序是啥？有啥用？
生活类比
> 你有一副乱序的扑克牌：5, 2, 8, 1, 9，想把它排成 1, 2, 5, 8, 9。
排序就是把数据按一定规则重新排列（从小到大 / 从大到小）。
为什么需要排序？
场景 没排序 排好序 找最大值/最小值 要遍历一遍 直接取第一个/最后一个 找中位数 很麻烦 直接取中间位置 查成绩排名 不知道第几名 一看就知道 二分查找 用不了 嗖嗖快
> 💡 记住：排序让数据变得有秩序，后续操作会方便很多！
二、冒泡排序（BUBBLE SORT）—— 像气泡一样往上冒
1. 核心思想
> 相邻两个数比较，大的往后“冒”，就像水里的气泡一样，大的气泡慢慢浮到水面。
每一轮会把当前未排序部分的最大值“冒泡”到最后面。
2. 图解过程
3. 代码实现
4. 关键点
要点 说明 外层循环 i 表示第几轮，需要 n-1 轮 内层循环 j 每轮比较 n-i 次（因为后面已经排好了） 交换条件 a[j] > a[j+1] → 大的往后冒 时间复杂度 O(n²)（慢，数据多了不行）
5. 优化版（加标记）
> 💡 如果某一轮没有发生任何交换，说明已经有序了，可以提前结束。
6. 特点总结
特点 说明 ✅ 优点 代码简单，容易理解 ❌ 缺点 太慢了，数据多的时候不实用 稳定性 ✅ 稳定（相等元素不交换，顺序不变） 适用场景 初学者入门，数据量小（n ≤ 1000）
三、选择排序（SELECTION SORT）—— 每次选最小的
1. 核心思想
> 每一轮在未排序部分选最小的，放到最前面。
就像你在打扑克牌时，每次从手牌里找出最小的那张放最前面。
2. 图解过程
3. 代码实现
4. 关键点
要点 说明 外层循环 i 表示放第 i 个位置（从第1个到第 n-1 个） 内层循环 j 在 i+1 到 n 中找最小值的位置 交换 把最小值和第 i 个位置交换 时间复杂度 O(n²)（还是慢）
5. 特点总结
特点 说明 ✅ 优点 代码简单，交换次数少（最多 n-1 次） ❌ 缺点 还是 O(n²)，数据多了慢 稳定性 ❌ 不稳定（相等元素可能改变顺序） 适用场景 数据量小，交换操作代价高的场景
四、插入排序（INSERTION SORT）—— 像整理扑克牌
1. 核心思想
> 把当前元素插入到前面已经排好序的序列中的正确位置。
就像你打扑克牌时，每次抓一张新牌，就插到手牌中正确的位置。
2. 图解过程
3. 代码实现
4. 关键点
要点 说明 从第2个开始 第1个元素默认已经排好了 向前比较 从后往前找，比 key 大的都往后挪 插入位置 j + 1 就是 key 的正确位置 时间复杂度 O(n²)（最坏情况），O(n)（最好情况）
5. 特点总结
特点 说明 ✅ 优点 数据基本有序时特别快（O(n)） ❌ 缺点 数据乱序时还是 O(n²) 稳定性 ✅ 稳定 适用场景 数据量小，或者数据基本有序
五、桶排序（BUCKET SORT）—— 用“桶”来分类放
1. 核心思想
> 准备一排“桶”（数组），每个桶代表一个数字，出现一次就往对应桶里丢一个标记。
这种排序不是比较大小，而是统计每个数字出现了多少次，然后按顺序输出。
2. 图解过程
3. 代码实现
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？
需要头文件：
基本语法：
3. 排序数组（从小到大）
> ⚠️ 注意：sort 默认下标从 0 开始！如果你习惯用 a[1]~a[n]，要这样写：
4. 从大到小排序（加第三个参数）
5. 自定义排序规则（高级用法）
如果你想按自己的规则排序，可以自己写一个比较函数：
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 一行搞定，最快最方便！
🔥 预习小任务
1. 冒泡排序中，为什么内层循环是 j <= n - i？
2. 选择排序和冒泡排序，哪个交换次数更少？
3. 如果要对 100000 个数据进行排序，上面哪种排序最合适？
4. sort(a + 1, a + n + 1) 中，为什么结束地址是 a + n + 1 而不是 a + n？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
明天上课带着这些问题来，效果翻倍！🚀
