20.化大为小桶排序（教学课件）-五年级信息科技全一册同步备课系列（人教版2024）

化大为小桶排序 化大为小桶排序 五年级全一册 行业PPT模板http:///hangye/ 人教版 分析桶排序的算法 桶排序的优势与不足 学科网 导 入 新 课 导 入 新 课 前面我们学习的选择排序、冒泡排序有什么共同点呢？ 它们都需要进行比较，根据比较的结果决定是否交换位置。 选择排序和冒泡排序都属于比较类排序，我们今天要介绍一种非比较类排序——桶排序。 讲 授 新 知 讲 授 新 知 一、分析桶排序的算法 老师收到了 50 位同学参加朗诵活动的报名信息表，这些同学来自一至五年级各班。现在这些信息表处于混乱状态，老师希望把这些信息表按照报名同学的年龄从小到大排序。 现在请你帮助老师想一个方法来完成这个任务。 信息表中所填年龄大小是实际岁数。例如，10.08 表示 10 岁 8 月，9.11 表示 9 岁 11 个月。 讲 授 新 知 讲 授 新 知 先把信息表中的年龄数据整理为表格。 这里的年龄数据比较多，如果使用选择排序或冒泡排序，处理时间比较长，桶排序是一种将大的数据量分解为小的数据量进行处理的分治思想。 年龄数据 10.11 10.07 11.08 7.01 7.05 7.04 8.07 10.07 7.07 9.08 11.05 10.02 11.07 7.08 10.04 8.07 11.02 9.04 9.10 8.04 11.02 10.09 10.11 11.09 9.02 9.06 8.05 7.06 8.10 10.05 9.07 9.05 8.11 7.04 11.06 10.03 10.09 9.11 9.09 11.11 10.10 7.10 8.08 11.04 7.02 11.11 8.05 7.09 7.09 8.09 表1：原始年龄数据 讲 授 新 知 讲 授 新 知 桶排序 假设输入数据是均匀分布的，那么可以将数据分到有限数量的桶里，每个桶再分别排序。 每个桶表示什么含义呢？ 讲 授 新 知 讲 授 新 知 桶排序中的“桶”代表的是一个数据区间范围，里面可以放置一个或多个数据，就像现实生活中的桶一样，能够作为容器使用。 讲 授 新 知 讲 授 新 知 桶排序的执行步骤主要有两步： 1.分配，即分配每个桶的数据区间，将所有数据依次放入对应的桶； 2.排序，对每个桶里的数据进行排序。 一至五年级的学生年龄通常有几个区间？ 我是7岁上一年级的，可以用大部分人的年龄做区间。 讲 授 新 知 讲 授 新 知 1.一至五年级的学生年龄区间可以分配如下： 7(含)-8岁 1 2 3 4 5 8(含)-9岁 9(含)-10岁 10(含)-11岁 11(含)-12岁 讲 授 新 知 讲 授 新 知 通过观察分析，基本操作步骤描述如下。 第 1 步：设置 5 个桶（数据区间），用于放置不同年龄段的信息表。 第 2 步：把所有年龄数据逐个放入对应的桶里，填写表格。 第 3 步：把每个桶里放入的信息表按年龄大小排序。 每个桶里的信息表数量较少，用前面学习过的排序方法很快就能完成。 第 4 步：依次取出 5 个桶里已经排好序的信息表，按桶号顺序组合到一起，全部信息表就排序完成了。 讲 授 新 知 讲 授 新 知 活动1：请同学们分组合作，将表1中的原始年龄数据分配到下表中。 桶1：7（含）至8岁 7.01 7.05 桶2：8（含）至9岁 8.07 8.07 桶3：9（含）至10岁 9.08 9.04 桶4：10（含）至11岁 10.11 10.07 桶5：11（含）至12岁 11.08 11.05 表2：分配到5个桶中的数据表（未排序） 讲 授 新 知 讲 授 新 知 活动2：将活动1中分配后的数据进行排序，填写到表3中。 桶1：7（含）至8岁 桶2：8（含）至9岁 桶3：9（含）至10岁 桶4：10（含）至11岁 桶5：11（含）至12岁 表3：对分配到5个桶中的数据表进行排序 讲 授 新 知 讲 授 新 知 对分配到5个桶中的数据表进行排序后，结果如下： 桶1：7（含）至8岁 7.01 7.02 7.04 7.05 7.06 7.07 7.08 7.09 7.09 7.10 桶2：8（含）至9岁 8.04 8.05 8.05 8.07 8.08 8.09 8.10 8.11 桶3：9（含）至10岁 9.02 9.04 9.06 9.07 9.08 9.09 9.10 9.11 桶4：10（含）至11岁 10.02 10.03 10.04 10.05 10.07 10.09 10.09 10.10 10.11 10.11 桶5：11（含）至12岁 11.02 11.02 11.04 11.05 11.06 11.07 11.08 11.09 11.11 11.11 表3：对分配到5个桶中的数据表进行排序 讲 授 新 知 讲 授 新 知 最后要对排序后的数据进行组合，得到最终排序结果。 7.01、7.02、7.04、7.05、7.06、7.07 、7.08、7.09、7.09、7.10、8.04、8.05、8.05、8.07、8.08、8.09、8.10、8.11、9.02、9.04、9.06、9.07、9.08、9.09、9.10、9.11、10.02 、10.03、10.04、10.05、10.07、10.09、10.09、10.10、10.11、10.11、11.02、11.02、11.04、11.05、11.06、11.07、11.08、11.09、11.11、11.11 讲 授 新 知 讲 授 新 知 通过上述操作，可以总结桶排序算法的一般步骤。 1. 创建桶，确定桶的区间范围和数量。 2. 把所有数据逐个放入对应的桶中。 3. 对每个桶内的数据进行排序。 4. 按照桶的顺序把数据组合起来。 桶排序体现了化大为小、分而治之的问题分解思想。当要处理的数据较多而且数值分布较为均匀时，这种方法具有明显的优势。 讲 授 新 知 讲 授 新 知 二、桶排序的优势与不足 讨论交流：桶排序有哪些优势？又存在哪些不足？ 1. 比如从数据量来分析，数据量分别是20个、500个、1 000个、100 000个等时的排序情况。 2. 可以通过网络搜索这一问题并阅读，小组同学一起分析讨论，确定主要结论并在全班交流分享。 讲 授 新 知 讲 授 新 知 1. 面对大量数据，没办法将所有数据一次处理完成时，可以分成一定数量的桶来分别处理； 2. 在数据分布均匀时，具有较高的排序效率，因为桶排序将数据分散到多个桶中独立进行排序，不需要逐个比较和交换数据； 3. 可以灵活调整桶的数量，优化桶排序的性能； 4. 通过在每个桶中使用稳定性较好的排序算法，可以保证桶排序的稳定性。 主要优势 讲 授 新 知 讲 授 新 知 1. 桶排序需要预先知道待排序数据的范围，否则无法合理设置桶的数量； 2. 数据分布不均匀时影响排序效率，某些桶可能会比其他桶集中了更多的数据，导致排序效率下降； 3. 对于大量重复数据，因某些桶数据过多而增加排序时间。 主要不足 拓 展 与 提 升 拓 展 与 提 升 1. 在学校组织的参观博物馆活动中，需要为来自不同年级五个班的同学安排车辆和座位。具体情况：如果每个班安排一辆车，车辆座位数不够；如果每个班安排两辆车，每辆车都会有空位置。 请你思考：如何规划同学乘车的问题？这个过程中是否存在算法？ 拓展活动 利用桶排序的算法思想。 1.先把五个班所有同学按学号进行分组排序，汇总到一起。 2.再按照车辆的顺序号及座位数安排座位。 拓 展 与 提 升 拓 展 与 提 升 2. 通过搜索引擎或生成式人工智能应用软件查找：还有哪些常用的排序算法？它们各有什么特点？排序算法可以解决哪些生活与学习问题？ 拓展活动 总 结 总 结 1. 认识桶排序算法，能够使用自然语言描述桶排序算法的执行步骤。 2. 了解桶的数量和范围在桶排序中的作用，感受将大的数据量化大为小的分治思想。 3.认识到不同算法具有不同执行效率、不同算法具有不同应用场合。 谢谢观看 学科网制作 Lavf59.27.100 Packed by Bilibili XCoder v2.0.2 $$我们先来看这个动画，这样的排序方式我们称作统排序。今天我们就来看一看它的具体过程。这些是我们要排序的数字，这些是我们准备的桶，每个桶接收的数字范围不一样。第一步分配遍历数组，将各数字分配到对应的桶中，4十九大于40小于60，所以分配到第三个桶中，9十六大于80，小于100分配到第五个桶中，后面的数字也按照范围分配到对应的桶中。分配好后就进行第二步排序，对每个桶中的数字进行排序，可以采用编程语言内置的排序函数。最后一步是合并，按照统从小到大的顺序合并。结果桶排序使用了分治策略，是一种非比较排序算法，给出参考代码，你们可以用自己熟悉的语言自己实现。