小白记录日常学习
今日任务总览
| 步骤 | 内容 | 时间 |
|------|------|------|
| 1 | 看B站视频：5.1~5.4（共10节） | 54分钟 |
| 2 | 读下面的核心知识点 | 15分钟 |
| 3 | 手打并运行3个练习 | 50~70分钟 |
| 4 | 自检 | 10分钟 |
看视频指南
5.1 快速排序（4小节，25分钟）
| 小节 | 集号 | 标题 |
|------|:--:|------|
| 5.1.1 | P114 | 算法概述 |
| 5.1.2 | P115 | 选主元 |
| 5.1.3 | P116 | 子集划分 |
| 5.1.4 | P117 | 算法实现 |
5.2 表排序（2小节，13分钟）
| 小节 | 集号 | 标题 |
|------|:--:|------|
| 5.2.1 | P118 | 算法概述 |
| 5.2.2 | P119 | 物理排序 |
> 表排序和多关键字排序以理解概念为主，无独立练习。
5.3 基数排序（3小节，12分钟）
| 小节 | 集号 | 标题 |
|------|:--:|------|
| 5.3.1 | P120 | 桶排序 |
| 5.3.2 | P121 | 基数排序 |
| 5.3.3 | P122 | 多关键字的排序 |
5.4 排序算法的比较（1小节，4分钟）
| 小节 | 集号 | 标题 |
|------|:--:|------|
| 5.4.1 | P123 | 排序算法的比较 |
核心知识点（视频精华）
一、快速排序（P114-P117）
> 选基准 → 小的放左边、大的放右边 → 递归排两边。
| 步骤 | 说明 |
|------|------|
| 选主元 | 选一个数作为"分界"（通常选最右或中位数） |
| 划分 | 比 pivot 小的放左边，大的放右边 |
| 递归 | 对左右两半重复同样操作 |
时间复杂度：O(n log n) 平均，O(n²) 最坏。不稳定。
二、表排序（P118-P119）
> 数据太大搬不动？只排"索引表"，不搬数据本身。
适用场景：数据元素很大（如结构体数组），交换成本高。
三、桶排序 / 基数排序（P120-P122）
> 桶排序：数据分桶 → 桶内排序 → 合并
> 基数排序：按位（个位→十位→百位）逐轮分桶收集
时间复杂度：O(n) ~ O(n log n)。稳定（基数排序）。
四、排序算法总结（P123）
| 算法 | 平均 | 最坏 | 稳定？ |
|------|:--:|:--:|:--:|
| 冒泡 | n² | n² | 是 |
| 插入 | n² | n² | 是 |
| 希尔 | n¹·³ | n² | 否 |
| 选择 | n² | n² | 否 |
| 堆 | n log n | n log n | 否 |
| 归并 | n log n | n log n | 是 |
| 快速 | n log n | n² | 否 |
| 基数 | O(n) | O(n) | 是 |
> 基数排序复杂度实际为 O(d×(n+k))，d为位数、k为基数。表中 O(n) 为简化描述。
动手练习
| | 练习 | 对应视频 | 文件名 |
|---|------|:--:|--------|
| 1 | 快速排序 | P114-P117 | `practice1_quicksort.c` |
| 2 | 桶排序 | P120-P121 | `practice2_bucket.c` |
| 3 | 排序算法耗时对比 | P123 | `practice3_sort_compare.c` |
练习1：快速排序
对应 P114-P117：快速排序最核心的是"分区"逻辑，用纸画出第一轮的分区过程。
练习2：桶排序
对应 P120-P121：分桶→桶内排序→收集，理解这个流程就懂了基数排序的思想。
练习3：排序对比
对应 P123：同一组数据，三种排序的耗时差多少？亲眼看到 O(n²) 和 O(n log n) 的差距。measure() 中 `void (sort)(int[], int)` 是函数指针——看不懂语法没关系，看调用方式 `measure(bubble_sort, ...)` 就行。
今日自检
- [ ] 能说出快速排序的三个步骤（选基准→分区→递归）
- [ ] 能解释桶排序的分桶→排序→收集流程
- [ ] 能说出至少三种 O(n log n) 和三种 O(n²) 的排序算法
- [ ] 三个练习都编译运行成功
明天预告
第6天：自选项目一 —— 学生管理系统
