一、先解答上次的 思考题
图：顶点 0 1 2 3，边：0-1、0-2、1-2、2-3从 0 开始 BFS 典型顺序：0 1 2 3
二、今天学习目标
- 了解排序算法的分类与指标
- 掌握冒泡排序
- 掌握选择排序
- 掌握插入排序
- 完整可运行代码 + 复杂度总结
三、排序基础概念
- 稳定排序：相等元素前后顺序不变
- 时间复杂度：执行快慢
- 空间复杂度：占用额外内存多少
今天这三个都是：
- 简单直观
- 时间复杂度O(n²)
- 适合小规模数据
四、1. 冒泡排序（Bubble Sort）
思想：两两比较，大的往后 “冒”，每轮冒出一个最大值。
// 冒泡排序 void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }五、2. 选择排序（Selection Sort）
思想：每轮选最小的，放到已排序区间末尾。
// 选择排序 void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } // 交换 int temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp; } }六、3. 插入排序（Insertion Sort）
思想：像摸牌一样，把当前数插入前面已经排好的序列里。
// 插入排序 void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }七、完整测试代码
#include <stdio.h> // 三种排序函数放这里 …… // 打印数组 void printArr(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr1[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr1) / sizeof(arr1[0]); printf("原数组："); printArr(arr1, n); // 测试冒泡 bubbleSort(arr1, n); printf("冒泡排序后："); printArr(arr1, n); return 0; }运行结果
原数组：5 2 9 1 5 6 冒泡排序后：1 2 5 5 6 9八、复杂度对比表
表格
| 排序 | 最好 | 最坏 | 平均 | 稳定 | 原地 |
|---|---|---|---|---|---|
| 冒泡 | O(n) | O(n²) | O(n²) | 稳定 | 是 |
| 选择 | O(n²) | O(n²) | O(n²) | 不稳定 | 是 |
| 插入 | O(n) | O(n²) | O(n²) | 稳定 | 是 |
记忆口诀：
- 冒泡：两两交换
- 选择：选最小放前面
- 插入：摸牌插位置
九、今日小练习
对数组{3, 1, 4, 2, 7, 5}分别用三种排序实现并输出结果。
