5.3.2冒泡排序（讲课）课件　2022—2023学年粤教版（2019）高中信息技术选修1

鱼吐泡泡 粤教版选择性必修一 ——冒泡排序 回顾：认识排序 排序是把一个任意序列的数据元素排列成按照某关键字的一个有序序列的过程 游戏：探究人如何实现排序 四位同学，随意排好顺序，从第一位同学开始往后排序，每位同学只能和后面一位同学交换位置，最终按学号从小到大的顺序排列。 如何一步步实现排序 什么时候结束排序 游戏：探究人如何实现排序 相邻比较 逆序交换 VS 冒泡排序 多轮排序 数列有序 核心步骤 鱼吐泡泡 冒泡排序过程就像鱼在水里冒泡的过程，小泡泡在下面，大泡泡在上面 2 5 9 1 3 5 3 2 9 1 鱼吐泡泡 冒泡排序是交换排序算法。依次进行大小比较来交换相邻两个逆序数据元素，冒泡排序中每一轮会确定一个数据的位置，逐步将待排序列变成有序序列。 任务一：人工进行学号的冒泡排序 在学习单上尝试人工解决排序问题，得到答案 时间：3分钟 3 5 2 6 8 排序过程 初始 6 3 8 5 2 第1遍 第2遍 第3遍 第4遍 3 5 2 6 8 3 2 5 6 8 3 6 5 2 8 2 3 5 6 8 相邻元素比较、逆序交换 多轮排序 从第一个元素到最后一个元素 冒泡排序基本思想 初始 6 3 8 5 2 第1遍 第2遍 第3遍 第4遍 1.假设有n个待排序元素，从第一个元素开始，相邻两个元素进行大小比较，根据结果交换位置，第一轮排序结束后最大的元素会移动到末尾。 2.按照上述方法进行第二轮排序，第二大的元素会移动到倒数第二个位置。 3. 经过n-1轮排序后，整个序列就是一个有序序列 3 6 5 2 8 3 5 2 6 8 3 2 5 6 8 2 3 5 6 8 冒泡排序 如果待排序的数据量达到上万、上百万，甚至更大，如何快速地利用冒泡排序来解决问题 人工排序 电脑排序 冒泡排序算法+计算机 冒泡排序算法分析 相邻元素比较、逆序交换 从第一个元素到最后一个元素 多轮排序 分支结构 循环结构 循环结构 算法： 循环列举第一个元素到最后一个元素： 循环进行下列步骤： 直到所有元素有序排列，程序结束 如果相邻两个元素满足大小条件： 交换相邻两个逆序元素的位置 流程图 开始 r[0]>r[1] r[0]和r[1]交换位置 Y N j=j+1 j=0 r[3]>r[4] r[3]和r[4]交换位置 Y N ····· 开始 j=0 j<n-1 r[j]和r[j+1]交换位置 Y j=j+1 Y r[j]>r[j+1] N 结束 N 结束 12 流程图 开始 r[j]>r[j+1] i=0 r[j]和r[j+1]交换位置 Y N j=j+1 j<n-1 j=0 Y i=1 ····· 开始 结束 r[j]>r[j+1] i=0 r[j]和r[j+1]交换位置 Y N j=j+1 i<n-1 j<n-1 j=0 Y Y i=i+1 N N N 13 流程图 开始 结束 r[j]>r[j+1] i=0 r[j]和r[j+1]交换位置 Y N j=j+1 i<n-1 j<n-1 j=0 Y Y i=i+1 N N 多轮排序 每一轮排序 相邻比较、逆序交换 14 任务二：学号冒泡排序的代码实现与优化 基础任务：打开学号冒泡排序程序框架，完善核心部分 选做的进阶任务：自学拓展资料，完善学号冒泡排序优化代码的核心部分 时间：6分钟 任务二：学号冒泡排序的代码实现与优化 基础任务代码 进阶任务代码 冒泡排序解决问题的一般步骤 分析问题 设计算法 确定排序对象 确定交换条件 排序结束条件 循环与分支结构 程序实现 运行程序 编写代码 得到有序序列 任务二 结合学习单上的问题二，完成基础任务，选做进阶任务 小组讨论 任务二：考试分数排序的代码实现与优化 基础任务：打开学号冒泡排序程序框架，完成考试分数排序的代码实现 选做的进阶任务：自学拓展资料，完善考试分数冒泡排序优化代码的核心部分 时间：6分钟 程序对比 冒泡排序算法优化 一轮排序后没有发生交换则结束程序 上一轮最后发生交换的位置之前不再发生交换则结束程序 冒泡排序进一步优化 冒泡排序优化 任务三：考试分数排名的代码优化 要求：结合刚才的分析，完成程序再优化 时间：3分钟 任务三：考试分数排名的代码优化 冒泡排序算法优化小结 冒泡排序优化方法一： 一轮排序后没有发生交换则结束 冒泡排序优化方法二： 上一轮发生交换的位置之前不再发生交换则结束 交流与评价 现在整理自己之前编写的程序放到共享区域，在共享区域查看他人编写的冒泡排序程序并相互交流讨论，学习他人作品的优点。填写学习单上的自评与互评，进行反思总结。 课堂总结 相邻元素两两比较、逆序交换、多轮排序 每轮排序过程中，值小的元素向前移动，值大的元素向后移动 冒泡排序算法：双层循环与分支的嵌套