资源简介

第二课：排序算法
教学内容：
本课程以苹果排序为情境，引导学生探究选择排序、冒泡排序和快速排序等经典排序算法。在探讨这三种排序方法原理的过程中，学生将运用分解、抽象、建模等计算思维技巧，了解每种排序算法的基本特征，并使用图形化编程软件编写程序来体验算法的运行过程。
教学目标：
知道排序算法的含义，熟练掌握三种排序算法的原理，
2.能知道不同排序算法的效率，能根据实际情况选择合适的排序算法
教学重点：
(1)排序算法的含义。
(2)三种算法的应用。
教学难点：
三种算法的应用。
教学过程：
情境导入
师:学校正在举行智力运动会，其中一项挑战是：（看大屏幕）有10个大小相似但质量不同的苹果，参赛者可借助一架天平，将它们按照质量由小到大的顺序排列，用的时间最少且方法最好的选手获胜。你会怎么做呢
生: ......
师:按照质量给苹果进行排序，就是一个不断比较每两个苹果质量的过程。在这个比较过程中，每个苹果都要参与比较，但不同的排序算法会导致苹果比较的次数有所不同。
师:选择排序是一种简单直观的排序算法。它的原理是从序列头部开始逐步构建有序序列，对于未排序数据，逐个选择出其中最小者插入已排序序列的尾部。
教学过程：
选择排序
师:接下来我们使用选择排序的方法对10个苹果进行排序，每个编号位置放置一个苹果。大家跟着小试身手的步骤一起来试一下吧。
师:第一轮，找出10个苹果中质量最轻的
第1步，使用天平比较0号和1号位置的苹果。
如果0号位置的苹果重则交换两个苹果的位置，否则不交换。
生......
师:第2步，用第1步比较出质量轻的苹果q分别与2-9号苹果进行比较，如果重就交换，轻则不交换，即可找出质量最轻的苹果，并把它放到首位。思考总共比较了_______次。
生: .....
师：第二轮，找出 10个苹果中第二轻的
第1步，用1号位置的苹果，重复第一轮的步骤，选出第二轻的苹果思考总共比较了_____次。
第2步，将第二轻的苹果放置1号位置
师：将剩余的苹果按照前面的方法全部排好序，总共比较了你是怎样计算的
生：……
师:假设 10 只苹果的质量如表所示，思考如何补全程序，完成 10个苹果的选择排序程序。
完善程序
2、冒泡排序
师：冒泡排序是一种简单的排序算法，其重复访问待排序数组，在一次访问中，依次比较两个相邻元素，逆序时就交换，重复进行直到没有交换为止在排序过程中，大的数据往下沉，小的数据往上浮，就像气泡一样，便将这种排序算法形象地称为冒泡排序。
师:接下里我们跟着小试身手的内容，看一下怎样使用冒泡排序法给苹果进行排序。
生...
师:第一轮，找出10个苹果中质量最重的一个
第1步，从0号位置的苹果开始，0号与1号位置比较，如果0号位置的苹果较重，则交换，否则不交换，比较_____次。
第2步，从1号苹果开始重复第1步，分别与后面相邻的苹果比较，直到所有苹果比较完成，总共比较_____次。
生：……
师：第二轮，找出第二重的苹果。经过第一轮比较和排序，9号位置的革果已经是最重的了。第二轮中，继续采用第一轮的方法，从0-8号位置中选出最重的苹果，总共比较______次。
第三轮，重复第一轮的步骤，继续进行排序，直至所有苹果都完成3排序。最终，最轻的苹果在0号位置，最重的苹果在9号位置。
3、快速排序
师：快速排序是另外一种比较实用的排序方法，它通过一趟扫描将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以将整个数据变成有序序列。
师：我们继续跟着小试身手的内容，看一下怎样使用快速排序法给苹果进行排序。
生：……
师：第一轮，选择基准苹果，并将其余的苹果分成两部分第1步，在10 个苹果中选择1个作为基准值。
第2步，分别用天平比较基准苹果和其余的苹果，将比基准值重的苹果放在B组，将比基准值轻的苹果放在A组。根据两组的数量，即可确定基准苹果的位置，共比较_____次。
生：……
师：第二轮，在A组中选择一个苹果作为基准值，在B组中选择一个革果作为基准值，按照第一轮的方法再进行比较、分组，并确定基准苹果位置，A组比较____次，B组比较____次。
第三轮，重复第一轮的步骤，直到将所有苹果进行排序，总共比较____次。
4、排序算法的比较
师：请根据前三个小试身手的内容，分别将选择排序、冒泡排序和快速排序三种不同的算法在解决苹果排序问题时的比较次数，填写在表中。
生：
总结
排序算法广泛应用于多个领域，例如数据库查询中用于快速定位所需数据;搜索引擎中确保搜索结果按相关性排序;数据分析中帮助识别数据模式和趋势。此外，排序算法还在图像处理、网络安全、电子商务等领域发挥重要作用。如快速排序、归并排序和堆排序更为合适。此外，优化策略如改进基准元素的选择减少不必要的比较和交换操作，也能提高排序效率。好了，今天的课就上到这里了，接下来有两个习题大家可以做一下，检验一下自己本节课的学习成果吧。
挑战自我
课后习题
1、假设你有一堆卡片，想以最快的速度将它们由小到大排好。下列排序方法最快的一项是()
A.采用选择排序方式，逐一查找，从小到大排列
B.采用冒泡排序方式，让相邻卡片依次比大小，大的沉底，小的上浮
C.采用快速排序方式，任选一张卡片作为参照，将卡片分成两组，再对每一组重复相同的操作
D.将每张卡片试着放在各个位置，选择最合适的位置
2、有10个大小不同的数字，分别为5、2、9、1、7、4、8、6、3、0.将这些数字按照从小到大的顺序排列，你会用到哪几种排序方法 你觉得哪种方法最适合 为什么

展开更多......

收起↑