第二课：排序算法
教学内容：
本课程以苹果排序为情境，引导学生探究选择排序、冒泡排序和快
排序等经典排序算法。在探讨这三种排序方法原理的过程中，学生将
运用分解、抽象、建模等计算思维技巧，了解每种排序算法的基本特
征，并使用图形化编程软件编写程序来体验算法的运行过程。
教学目标：
1.知道排序算法的含义，熟练掌握三种排序算法的原理，
2.能知道不同排序算法的效率，能根据实际情况选择合适的排序算法
教学重点：
(1)排序算法的含义。
(2)三种算法的应用。
教学难点：
三种算法的应用。
教学过程：
一、情境导入
师:学校正在举行智力运动会，其中一项挑战是：（看大屏幕）有10
个大小相似但质量不同的苹果，参赛者可借助一架天平，将它们按照
质量由小到大的顺序排列，用的时间最少且方法最好的选手获胜。你
会怎么做呢?
生:
师:按照质量给苹果进行排序，就是一个不断比较每两个苹果质量的
过程。在这个比较过程中，每个苹果都要参与比较，但不同的排序算
法会导致苹果比较的次数有所不同。
师:选择排序是一种简单直观的排序算法。它的原理是从序列头部开
始逐步构建有序序列，对于未排序数据，逐个选择出其中最小者插入
已排序序列的尾部。
二、教学过程：
1、选择排序
师:接下来我们使用选择排序的方法对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组比较____次。
第三轮，重复第一轮的步骤，直到将所有苹果进行排序，总共比较____
次。