基础排序（插入、选择、冒泡）
插入排序、选择排序、冒泡排序是最简单的三种排序算法——时间复杂度 O(n²)，实现简单，适合小规模数据
🃏 为什么需要排序？
你的手机通讯录如果按名字乱序排列——想找”张三”得翻遍整个通讯录。按字母排序后，找人就快多了。
排序（Sorting）是计算机科学最基础、研究最深入的问题之一。虽然你平时编程直接调用 arr.sort() 就完事了，但理解排序算法的原理，能帮你建立”算法思维”——如何一步步把一个问题解决得越来越高效。
这一节先学三种最简单的排序——它们的时间复杂度都是 O(n²)，效率不高，但实现简单、思路直观，是理解算法设计的好起点。
📚 类比：整理一摞试卷
老师抱着一摞没排序的试卷，想要按学号排好。不同老师有不同的整理方式：
- 冒泡排序：从头到尾扫一遍，发现相邻两张顺序不对就交换——像气泡上浮一样，大的逐渐沉到底
- 选择排序：每次从剩下的试卷里找出学号最小的，放到最前面
- 插入排序：一张一张地拿起来，插入到已经排好序的试卷堆中——像整理扑克牌
三种方式都能排好，但”快”和”慢”不一样。
💨 冒泡排序（Bubble Sort）——像气泡一样上浮
思路
从头到尾遍历数组，比较相邻的两个元素，如果顺序不对就交换它们。每一轮遍历后，最大的元素就像气泡一样”浮”到末尾。
过程演示
原始：[5, 3, 8, 6, 4]
第 1 轮（把最大的 8 浮到最后）：
5 和 3 比 → 交换 → [3, 5, 8, 6, 4]
5 和 8 比 → 不动 → [3, 5, 8, 6, 4]
8 和 6 比 → 交换 → [3, 5, 6, 8, 4]
8 和 4 比 → 交换 → [3, 5, 6, 4, 8] ← 8 到位了
第 2 轮（把第二大的 6 浮到倒数第二位）：
3 和 5 比 → 不动 → [3, 5, 6, 4, 8]
5 和 6 比 → 不动 → [3, 5, 6, 4, 8]
6 和 4 比 → 交换 → [3, 5, 4, 6, 8] ← 6 到位了
第 3 轮：
3 和 5 比 → 不动 → [3, 5, 4, 6, 8]
5 和 4 比 → 交换 → [3, 4, 5, 6, 8] ← 5 到位了
第 4 轮：
3 和 4 比 → 不动 → [3, 4, 5, 6, 8] ✅ 排好了
代码实现
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 一共 n 轮
swapped = False # 优化：如果这一轮没交换，说明已经有序
for j in range(n - 1 - i): # 每轮的比较范围缩小
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 没发生交换 → 提前结束
break
return arr
特点
| 维度 | 值 |
|---|---|
| 最好情况 | O(n)——已有序，加优化后一轮搞定 |
| 平均情况 | O(n²) |
| 最坏情况 | O(n²)——完全逆序 |
| 空间复杂度 | O(1)——原地排序 |
| 稳定性 | ✅ 稳定（相等元素不交换） |
🎯 选择排序（Selection Sort）——每次挑最小的
思路
每次从未排序的部分中选出最小的元素，放到已排序部分的末尾。
原始：[5, 3, 8, 6, 4]
↑未排序区域
第 1 轮：从 [5, 3, 8, 6, 4] 中选出最小的 3，和位置 0 的 5 交换
[3, 5, 8, 6, 4]
↑未排序区域
第 2 轮：从 [5, 8, 6, 4] 中选出最小的 4，和位置 1 的 5 交换
[3, 4, 8, 6, 5]
↑未排序区域
第 3 轮：从 [8, 6, 5] 中选出最小的 5，和位置 2 的 8 交换
[3, 4, 5, 6, 8]
↑未排序区域
第 4 轮：从 [6, 8] 中选出最小的 6，交换 → [3, 4, 5, 6, 8] ✅
代码实现
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
🧩 类比：体育课排队
老师让同学们按身高从矮到高排成一排。
选择排序的做法：老师先扫视全班，找到最矮的同学，让他站到第一位。然后从剩下的人中找最矮的，站到第二位……以此类推。
无论原来的队伍有多乱，老师总是做同样的事——每次找到”当前最矮的”。
特点
| 维度 | 值 |
|---|---|
| 最好/平均/最坏 | 都是 O(n²)——因为每轮都要扫描完整找最小 |
| 空间复杂度 | O(1)——原地排序 |
| 稳定性 | ❌ 不稳定（交换可能改变相等元素的相对顺序） |
💡 选择排序不管数据原来是什么顺序，都是 O(n²)——它每轮都要做完整的扫描。不像冒泡排序有”提前结束”的优化机会。
🃏 插入排序（Insertion Sort）——像整理扑克牌
思路
把数组分成”已排序”和”未排序”两部分，每次从未排序部分取一个元素，插入到已排序部分的正确位置。
原始：[5, 3, 8, 6, 4]
↑已排序部分只有第一个元素
第 1 轮：取 3，插入到 [5] 的正确位置
→ [3, 5, 8, 6, 4]
↑已排序部分扩展
第 2 轮：取 8，已比 [3,5,8] 中所有大 → 不动
→ [3, 5, 8, 6, 4]
↑
第 3 轮：取 6，插入到 [3,5,8] → [3,5,6,8]
→ [3, 5, 6, 8, 4]
↑
第 4 轮：取 4，插入到 [3,5,6,8] 的正确位置
→ [3, 4, 5, 6, 8] ✅
代码实现
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # 当前要插入的元素
j = i - 1
# 把比 key 大的元素往后移
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 把 key 放到正确位置
return arr
🃏 类比：整理扑克牌
你抓了一手牌，从左到右整理。你拿起一张新牌（key），从右向左和手中的牌比较，找到它应该在的位置插进去。
手中已有的牌总是排好序的——新牌只要找到位置插入就行。
特点
| 维度 | 值 |
|---|---|
| 最好情况 | O(n)——已经有序，每轮只需比较一次 |
| 平均情况 | O(n²) |
| 最坏情况 | O(n²)——完全逆序 |
| 空间复杂度 | O(1)——原地排序 |
| 稳定性 | ✅ 稳定 |
💡 插入排序的一个重要特性：在数据基本有序的情况下，插入排序非常快（接近 O(n)）。因此一些高级排序（如 Timsort，Python 和 Java 的默认排序）在数据量小时会切换到插入排序。
⚔️ 三种排序对比
| 算法 | 思想 | 最好 | 平均 | 最坏 | 稳定 | 特点 |
|---|---|---|---|---|---|---|
| 冒泡 | 相邻交换，大数沉底 | O(n) | O(n²) | O(n²) | ✅ | 最简单，但最慢 |
| 选择 | 每轮选最小放前面 | O(n²) | O(n²) | O(n²) | ❌ | 稳定 O(n²)，不适合有序数据 |
| 插入 | 把元素插入已排序部分 | O(n) | O(n²) | O(n²) | ✅ | 基本有序时接近线性 |
什么时候用？
- 数据量很小（<50）：三种都可以，插入排序通常略好
- 数据基本有序：插入排序（接近 O(n)）
- 只是为了学习算法：三种都值得自己实现一遍
- 实际开发：用标准库的
sorted()或arr.sort()就行——它们用的是 Timsort（归并排序的优化版，后面讲高级排序时会提到）
📝 小结
| 概念 | 一句话 |
|---|---|
| 冒泡排序 | 相邻比较交换，大的像气泡一样浮到末尾 |
| 选择排序 | 每轮选最小放到已排序末尾 |
| 插入排序 | 像整理扑克牌，把元素插入已排序部分 |
| O(n²) | 这三种排序在小规模数据下可用 |
| 稳定性 | 相等元素排序前后的相对顺序不变 |
🎯 小练习：给定
[7, 2, 5, 1, 9, 3]，手动模拟插入排序的每一步过程，写出每轮结束后数组的状态。
为什么先学这个？ 理解基础排序的局限（O(n²) 对大数组太慢），下一步学习更高效的高级排序（归并、快排、堆排）。