> **GESP等级：四级 | 考级考点：GESP Python 四级** # 第15节：选择排序与插入排序——选秀与摸牌 --- ## 一、课程概览 | 项目 | 内容 | |------|------| | 课程名称 | 选择排序与插入排序——选最矮的&摸牌游戏 | | 课程时长 | 60分钟 | | 教学形式 | 双故事导入 + 动作模拟 + turtle对比动画 + 动手编程 | | 核心目标 | 理解选择排序和插入排序的原理，对比两种排序的异同 | ### 教学目标 | 维度 | 目标描述 | |------|----------| | 知识目标 | 掌握选择排序（选最小的放前面）和插入排序（新牌插入合适位置） | | 技能目标 | 能写出两种排序的Python代码，用turtle画出对比动画 | | 思维目标 | 理解"选择 vs 插入"两种不同思路，培养多角度思考 | | 情感目标 | 感受不同算法解决同一问题的乐趣，理解"条条大路通罗马" | ### 教学重点与难点 | 类型 | 内容 | |------|------| | 重点 | 选择排序找最小元素的方法；插入排序的"向前比较插入" | | 难点 | 插入排序中元素后移的逻辑 | | 易错点 | 选择排序中min_idx的更新；插入排序中j的循环条件 | --- ## 二、教学准备 ### 教具准备 1. 电脑+Python环境（已安装turtle库） 2. 投影仪/大屏幕（展示对比动画） 3. 数字卡片两套：写有5,3,1,4,2的卡片 4. 一副扑克牌（演示插入排序） 5. "选秀"头饰/标签（选中最矮的给他戴上） 6. 计时器（对比两种排序速度） ### 课前准备 - 打开两个turtle窗口并排显示（左右对比） - 测试两种排序的动画代码 - 准备好扑克牌演示道具 - 制作"最矮"标签卡 --- ## 三、教学过程（60分钟） --- ### 第一部分：导入环节（10分钟）——选秀与摸牌 #### 1.1 故事一：选秀节目（3分钟） "小朋友们，你们看过选秀节目吗？" "比如《中国好声音》《创造营》——评委要从一堆选手里选出最棒的！" "今天我们来玩一个'选秀游戏'！" "老师这里有很多数字选手：`[5, 3, 1, 4, 2]`" "我们要把最矮的（最小的）选出来，让他站第一位！" **老师演示**： 1. 打乱5张数字卡片 2. "我要从这些选手中找出最矮的——1号在哪里？" 3. 找出1，把它放到第一位 4. "好了，剩下的选手 `[5, 3, 4, 2]` 继续选秀！" 5. 找出最小的2，放到第二位 6. "继续！找出最小的3，放到第三位..." 7. 直到全部排好！ "这就是**选择排序**——每次选出最小的，放到最前面！" #### 1.2 故事二：打扑克牌（3分钟） "小朋友们打过扑克牌吗？" "摸牌的时候，你摸到一张新牌，会怎么放？" **老师演示**（用扑克牌）： 1. 手中已有排好序的牌：3, 5, 7 2. 摸到一张新牌4 3. "4比5小，比3大，所以插到3和5中间！" 4. 手中变成：3, 4, 5, 7 "这就是**插入排序**——每次把新牌插入到合适的位置！" #### 1.3 身体游戏：两种排序模拟（4分钟） **游戏1：选秀排序（选择排序）** 选5个孩子上台站一排。 1. 老师喊："找出最矮的！" → 孩子们互相看，找出最矮的 2. 最矮的站到左边第一位 3. "在剩下的里面找最矮的！" → 找第二矮的站第二位 4. 重复直到全部排好 > **身体锚点**："找最矮→放前面"——食指在眼前横扫"找"的动作，然后指向左边 **游戏2：摸牌排序（插入排序）** 选5个孩子，给每人发一张数字卡片，让他们按身高先排好（假装已经排好的手牌）。 1. 老师拿一张新数字卡片（如4） 2. "我要插入这张牌——比3大，比5小，插到中间！" 3. 站在3和5之间的位置 4. 后排的孩子依次往后挪一位 > **身体锚点**："看牌→找位置→插入"——手放额头做"看"的动作，然后做"插"的动作 --- ### 第二部分：知识点讲解（20分钟） --- ### 选择排序（10分钟） #### 2.1 选择排序原理（3分钟） **核心思想**： > **"每轮选最小的，放到最前面"** **步骤**： 1. 在整个数组中找最小的元素 2. 把它放到第1个位置（跟第1个交换） 3. 在剩下的元素中找最小的 4. 放到第2个位置（跟第2个交换） 5. 重复直到全部排好 **口诀**： > "选择排序选最矮，放到前排再继续" > "剩下里面再选矮，依次排好不拥挤" #### 2.2 选择排序分步演示（5分钟） **初始数组**：`[5, 3, 1, 4, 2]` **第1轮**：在[5,3,1,4,2]中找最小的 - 扫描：5→3→1→4→2，发现1最小 - 1跟第1位的5交换 → `[1, 3, 5, 4, 2]` - ✅ 第1位排好了！ **第2轮**：在[3,5,4,2]中找最小的 - 扫描：3→5→4→2，发现2最小 - 2跟第2位的3交换 → `[1, 2, 5, 4, 3]` - ✅ 前2位排好了！ **第3轮**：在[5,4,3]中找最小的 - 扫描：5→4→3，发现3最小 - 3跟第3位的5交换 → `[1, 2, 3, 4, 5]` - ✅ 前3位排好了！ **第4轮**：在[4,5]中找最小的 - 扫描：4→5，发现4最小 - 4已经在第4位，不用换 - ✅ 全部排好了！ **最终结果**：`[1, 2, 3, 4, 5]` #### 2.3 代码实现（2分钟） ```python def selection_sort(arr): n = len(arr) for i in range(n-1): # 需要n-1轮 min_idx = i # 假设第i位是最小的 for j in range(i+1, n): # 在剩下的中找更小的 if arr[j] < arr[min_idx]: # 找到了更小的 min_idx = j # 更新最小值的索引 if min_idx != i: # 如果最小值不是当前位 arr[i], arr[min_idx] = arr[min_idx], arr[i] # 交换 return arr ``` **关键点解释**： - `min_idx = i`：先假设第i个是最小的（"先选当前的选手"） - `for j in range(i+1, n)`：在后面的选手中找（"看看后面有没有更矮的"） - `if arr[j] < arr[min_idx]`：找到了更矮的（"这个更矮！"） - `min_idx = j`：更新最矮的为j（"换人！"） - 交换：把最矮的放到前面（"最矮的站最前面"） --- ### 插入排序（10分钟） #### 2.4 插入排序原理（3分钟） **核心思想**： > **"每次把新元素插入到前面已排好的序列中"** **步骤**： 1. 从第2个元素开始，把它当作"新摸到的牌" 2. 跟前面的元素比较，找到合适的位置 3. 把比它大的元素往后移一位 4. 把它插进去 **口诀**： > "插入排序像摸牌，新牌插入合适位" > "前面后移留位置，插进去就排好队" #### 2.5 插入排序分步演示（5分钟） **初始数组**：`[5, 3, 1, 4, 2]` **第1步（i=1）**：摸到3 - 前面的牌：[5] - 3比5小 → 5往后移一位 → [5, 5, 1, 4, 2] - 把3插到第0位 → [3, 5, 1, 4, 2] - ✅ 前2位排好：3, 5 **第2步（i=2）**：摸到1 - 前面的牌：[3, 5] - 1比5小 → 5后移 → [3, 5, 5, 4, 2] - 1比3小 → 3后移 → [3, 3, 5, 4, 2] - 把1插到第0位 → [1, 3, 5, 4, 2] - ✅ 前3位排好：1, 3, 5 **第3步（i=3）**：摸到4 - 前面的牌：[1, 3, 5] - 4比5小 → 5后移 → [1, 3, 5, 5, 2] - 4比3大 → 停！插到3后面 → [1, 3, 4, 5, 2] - ✅ 前4位排好：1, 3, 4, 5 **第4步（i=4）**：摸到2 - 前面的牌：[1, 3, 4, 5] - 2比5小 → 5后移 → [1, 3, 4, 5, 5] - 2比4小 → 4后移 → [1, 3, 4, 4, 5] - 2比3小 → 3后移 → [1, 3, 3, 4, 5] - 2比1大 → 停！插到1后面 → [1, 2, 3, 4, 5] - ✅ 全部排好！ #### 2.6 代码实现（2分钟） ```python def insertion_sort(arr): n = len(arr) for i in range(1, n): # 从第2个开始摸牌 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 # 插入到合适位置 return arr ``` **关键点解释**： - `key = arr[i]`：摸到的新牌（要插入的元素） - `j = i - 1`：从已排好序列的最右边开始比 - `while j >= 0 and arr[j] > key`：往前找，直到找到比key小的或到最前面 - `arr[j + 1] = arr[j]`：把比key大的元素往后移（腾位置） - `arr[j + 1] = key`：把key插入到空出来的位置 --- ### 两种排序对比（3分钟） #### 2.7 对比表格 | 对比项 | 选择排序 | 插入排序 | |--------|----------|----------| | 核心思想 | 选最小的放前面 | 新牌插入合适位置 | | 形象比喻 | "选秀" | "摸牌" | | 稳定性 | 不稳定 | 稳定 | | 最好情况 | O(n²) | O(n)（已排好） | | 最坏情况 | O(n²) | O(n²) | | 交换次数 | 最多n-1次 | 最多n(n-1)/2次 | #### 2.8 对比口诀 > "选择排序选最矮，放到前排再继续" > "插入排序像摸牌，新牌插入合适位" > "选择不稳定乱顺序，插入稳定很靠谱" > "选择交换少，插入挪动多" --- ### 第三部分：演示环节（10分钟）——turtle对比动画 #### 3.1 双窗口对比演示（5分钟） **老师操作**： 1. 运行选择排序与插入排序对比代码 2. 屏幕左边显示选择排序动画，右边显示插入排序动画 3. 两组完全一样的数据同步排序 **引导观察**： - "看左边！选择排序在'找最矮'，它需要来回扫描" - "看右边！插入排序在'摸牌插入'，它只管往前比" - "谁更快？谁交换的次数少？" #### 3.2 动画说明（3分钟） **选择排序动画特点**： - 每轮用黄色高亮扫描所有未排序元素 - 找到最小值后，用绿色标记 - 交换时两根柱子互换位置 **插入排序动画特点**： - 取出当前元素（用特殊颜色标记） - 往前逐个比较，比它大的柱子往后移动 - 找到位置后插入 #### 3.3 对比讨论（2分钟） **师生互动**： - 问："什么时候插入排序比选择排序快？" - 答："当数据接近排好时！因为插入排序可以很快找到位置" - 问："什么时候选择排序表现稳定？" - 答："无论数据怎么样，选择排序都要找n-1轮，总是比较同样多次数" --- ### 第四部分：实操环节（15分钟） #### 4.1 任务1：运行对比代码（3分钟） 1. 打开老师给的代码文件 2. 运行代码，看到两种排序的对比动画 3. 尝试修改数据，观察两种情况 #### 4.2 任务2：完成选择排序代码（4分钟） 补全代码： ```python def selection_sort(arr): n = len(arr) for i in range(_____): # n-1轮 min_idx = _____ # 假设当前是最小的 for j in range(_____, n): # 在剩下的中找 if arr[___] < arr[_____]: # 找到更小的 min_idx = _____ # 更新 if min_idx != i: arr[___], arr[_____] = arr[_____], arr[___] # 交换 return arr ``` #### 4.3 任务3：完成插入排序代码（4分钟） 补全代码： ```python def insertion_sort(arr): n = len(arr) for i in range(_____, n): # 从第2个开始摸牌 key = arr[___] # 当前摸到的牌 j = _____ # 前面牌的最后一个 while j >= 0 and arr[___] > key: # 往前找 arr[___ + 1] = arr[___] # 后移 j -= 1 arr[___ + 1] = _____ # 插入 return arr ``` #### 4.4 任务4：排序对比实验（4分钟） 用不同的数据测试两种排序，记录下来： | 数据 | 选择排序比较次数 | 插入排序比较次数 | 谁快？ | |------|-----------------|-----------------|--------| | [5,3,1,4,2] | | | | | [1,2,3,4,5]（已排好） | | | | | [5,4,3,2,1]（完全逆序） | | | | | 随机8个数 | | | | --- ### 第五部分：小测环节（5分钟） #### 5.1 选择题（3题） **第1题**：选择排序每轮要做什么？ - A. 相邻比较交换 - B. 找最小的放到最前面 ✅ - C. 把新牌插入合适位置 - D. 随机交换 **第2题**：插入排序中，当摸到一张新牌时，要把比它大的牌怎么处理？ - A. 删除 - B. 往前移一位 - C. 往后移一位 ✅ - D. 保持不变 **第3题**：下面的描述哪个是选择排序？ - A. "摸牌插入到合适位置" - B. "选最矮的站第一位" ✅ - C. "相邻两两相比较" - D. "像气泡一样往上冒" #### 5.2 判断题（2题） **第4题**：插入排序在数据已经排好时特别快。（✅） **第5题**：选择排序是稳定排序。（❌，是不稳定的） #### 5.3 对比连线题 把左边的描述连到右边的排序名称： | 描述 | 排序名称 | |------|----------| | 像摸牌插入 | 选择排序 | | 选最矮的放前面 | 插入排序 | | 需要元素后移 | 冒泡排序 | | 相邻两两比较 | 插入排序 | | 需要来回扫描找最小值 | 选择排序 | --- ## 四、课后延伸 ### 生活中的对应 - **选择排序**：老师在班级里选班长→选学习委员→选劳动委员 - **插入排序**：整理书包时，把新书按大小插到已有的书之间 ### 思维拓展 - 为什么选择排序不稳定？（相等的元素交换后位置变了） - 插入排序在什么情况下性能最好？（数据基本有序时） ### 下节预告 "今天我们学了'选秀'和'摸牌'两种排序方法。下节课我们要学习**递推算法**——一种从已知推出未知的神奇方法，比如兔子生兔子的问题！" --- ## 五、板书设计 ``` ╔══════════════════════════════════════════════════════════╗ ║ 选择排序 vs 插入排序 ║ ║ ║ ║ 选择排序 = 选秀 插入排序 = 摸牌 ║ ║ 每轮选最小放前面 新牌插入已排好序列 ║ ║ ║ ║ ┌─选择排序代码─┐ ┌─插入排序代码─┐ ║ ║ │min_idx = i │ │key = arr[i] │ ║ ║ │for j找更小 │ │j = i-1 │ ║ ║ │找到就交换 │ │while后移 │ ║ ║ └─────────────┘ │插入key │ ║ ║ └─────────────┘ ║ ║ ║ ║ 口诀： 口诀： ║ ║ 选择排序选最矮 插入排序像摸牌 ║ ║ 放到前排再继续 新牌插入合适位 ║ ║ 剩下里面再选矮 前面后移留位置 ║ ║ 依次排好不拥挤 插进去就排好队 ║ ╚══════════════════════════════════════════════════════════╝ ``` --- ## 六、课程反思 ### 教师自评要点 1. 孩子们是否能区分选择排序和插入排序？ 2. 扑克牌演示是否直观有效？ 3. 对比动画是否能帮助理解差异？ 4. 实操环节中两种排序的完成度如何？ ### 常见问题应对 - **孩子混淆两种排序**：用"选秀"（选最矮）和"摸牌"（插入）两个故事区分 - **不理解元素后移**：用"给新同学腾位置，大家都往后挪"来比喻 - **不理解不稳定**：演示[5,3,5,2]第一个5和3交换后，顺序变了 ### 教学调整建议 - 如果年龄偏小（7-8岁）：只讲选择排序，插入排序留到下次 - 如果时间充裕：增加"排序速度比赛"环节，用计时器对比 - 如果孩子兴趣浓厚：展示更多数据（20个数字）的排序动画