中小学教育资源及组卷应用平台
项目八 模拟实现商品排序
——常用排序算法及其比较
第一课时 尝试使用插入排序法实现商品销量排序
教材分析
本节的主要内容是尝试使用插入排序法实现商品销量排序。以生活中经常需要对某些数据进行查找和排序，如销售统计、商品查找等为主线，整个项目分为尝试使用插入排序法实现商品销量排序、尝试使用 泡排序法实现商品销量排序、尝试使用选择排序法实现商品销量排序、比较三种排序方法四部分。
本课时的学习中，学生将尝试使用直接插入排序、冒泡排序和直接选择排序等方法对模拟的网络购物平台中的店铺销售数据进行排序。在使用插入排序中的直接插人排序对6件商品销量数据进行排序的过程中，教材先给出了使用顺序存储结构下的排序示意图(部分)，然后在活动中要求学生完成剩下的步骤示意图以及链式存储结构下的排序过程描述，并完成算法流程图设计和程序的编写，最后上机运行得出结果。
本项目强调引导学生在理解、掌握三种排序方法的基础上，对它们的基本特点和稳定性进行分析。通过本项目的学习，学生能够掌握基本的排序方法，理解排序算法与数据结构的关系，从而学会根据实际问题选择恰当的算法完成数据的排序。
本节课时将从身边熟悉的事例出发，带领学生探究各种排序和查找算法，在学习过程中体验迭代和递归的方法，并理解算法与数据结构的关系，进一步发展学生的计算思维和数字化学习与创新的能力。
教学目标
1.掌握常用的数据排序方法——插入排序；
2.理解三种排序算法的特点。
3.理解排序算法与数据结构的关系。
4.能通过Python编程实现三种排序算法。
5.培养学生的信息意识和计算思维能力。
教学重点
1.掌握常用的数据排序方法；
2.理解排序算法与数据结构的关系。
教学难点
1.理解插入排序算法的特点；
2.培养学生的信息意识和计算思维能力。
教学方法
体验法、讲授法、讨论法、示例法
教学准备
计算机教室、多媒体设备、多媒体广播软件、Python编程环境、待排序的商品数据、教学课件等。
教学过程
一、新课导入
在日常生活中经常可以看到各种排行榜，如关注度排行榜、流行歌曲排行榜、球队实力排行榜、销量排行榜(图5-1)等。许多网络购物平台提供当月最畅销的商品排行。假如某店铺中某一种类商品只有6件不同价格的商品，若采用人工排序，由于数据量小，简单目测一下就可以得出排序结果。但实际上大部分情况下的排序数据可能会是成千上万条，因此，采用人工的方式会耗时多，且容易出错。若采用合理的数据结构和算法，编程实现后，系统便能对大量数据进行自动排序，省时省力，且只要程序正确，基本不会出错。
图5-1按销量排序页面
二、排序
将一组次序任意的数据元素转变为按其关键字(可以标识数据元素的某个数据项的值)递增(或递减)次序排列的过程，称为排序。例如，表5-2所示商品销售表可以按序号(主关键字，可以唯一标识一数据元素)递增进行排序，也可以按单价或销量(次关键字、可识别若干数据元素)进行排序。排序后，每个数据元素的顺序会按关键字的顺序排列。
排序方法有插入排序(直接插入排序、折半插入排序、希尔排序等)、交换排序(冒泡排序、快速排序)、选择排序(直接选择排序、堆排序等)、归并排序等。
序号 商品名称 单价（元） 销量（件）
0 文具盒1 10 190
1 文具盒2 15 170
2 文具盒3 12 180
…… …… …… ……
N-1 文具盒N-1 13 205
三、插入排序
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序 ( https: / / baike. / item / %E6%8E%92%E5%BA%8F / 1066239" \t "https: / / baike. / item / %E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F / _blank )方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。
小时候你一定玩过扑克牌，当你在整理那些乱序的牌的时候，你想到的第一种方法一定是将这些新摸到的牌插入到对应的位置，以此来达到手牌有序。
实现思路：
1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果 符合条件（比前面的大或者小，自定义），则让他们交换位置。
2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需 要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前 面的数据都是有序的。
3.重复步骤二，一直到数据全都排完。
让我们以数组为例，假设有下面的数组：
我们可以看到，前面3个元素已经有序，后面7个元素还是无序状态，这时候我们需要将第4个元素插入到相应的位置，这样有序序列就从3增加到4，无序序列就从7减小到6。
如果对于一个含有n个元素的完全无序的数组，我们可以把第一个元素视作有序，其余 n-1 个元素视为无序，因为只有一个元素的数组肯定是有序的，所以每次将无序序列的第n-1一个元素插入到相应位置后，问题的规模就减少1。如果我们重复 n-1 次，数组就从无序变为有序了。
最后我们用代码实现一下插入排序。
def insertion_sort(array):
for i in range(1, len(array)):
v = array[i]
j = i - 1
while j >= 0 and array[j] > v:
array[j+1] = array[j] # 用前一个元素覆盖当前元素
j = j - 1
array[j+1] = v # 循环结束后，将 v 插入到相应位置
return array
四、尝试使用插入排序法实现商品销最排序
若某家店铺某一类商品6个品种的月销量分别是21，25，49，25*，16，8，要对这些商品按销量进行排序，可采用顺序存储结构下的插入排序法，部分过程如图5-2所示。
图5-2插入排序部分过程
先将初始无序序列的6件商品销量数据存放在下标0~5某一数组中，然后将第一个商品销量数据21视作初始有序序列。将剩余的5件商品销量数据视作无序序列。接下来每次从无序序列中取第一个商品销量数据插入到有序序列的适当位置上。为了操作方便，插入的商品销量数据与有序序列中商品销量数据从后往前依次比较，一边比较一边将大的商晶销量数据往后移动，直至找到插入位置。
思考与讨论？
1.商品除了可以按销量排序外，还可以按什么排序？
建议教师引导学生观察商品的销售页面，归纳出价格、人气等排序关键字。
2.生活中还有哪些排序的例子？
例如：身高、年龄、体重等
五、课堂活动
1.参照上述步骤画出剩下的排序过程图。
2.若采用链式存储结构，请根据图5-3所示，用文字描述排序过程，并画出每个过程图。谈谈使用顺序存储结构和链式存储结构实现插人排序，各有何特点，以及具体的算法是否相同；在数据量小和大的情况下分别用哪一种比较好。
图5-3采用链式存储结构实现插入排序
参考答案：
插入排序过程(采用链式存储结构)：
(1)将原始链表断成有序链表和无序链表。有序链表包括头结点和第一个数据结点，指针Head指向头结点。无序链表包括第二个数据结点开始的所有结点，指针p指向第二个数据结点。
(2)通过指针P获得下一个需要排序数据25(无序链表的第一个节点)。在有序链表中查找第一个大于25的数据结点9,在结点之前插入结点25。若找不到大于25的数据节点，则将结点25插在有序链表的最后。结点25插入有序链表后，断开与无序链表的连接。指针指向无序链表的下一个结点49。
(3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下，
插入25:
插入49
插入25*：
插入16:
插入8:
顺序存储结构与链式存储结构的比較：
对于插入位置，顺序存储结构可以从有序序列的首部开始查找也可以从尾部开始查找。链式存储结构通过指针指向下一个结点，因而单链表只能从有序序列的首部开始查找
顺序存储结构在进行插入、删除元素等操作时，需要移动其他元素时间复杂度高。而链式存储结构在进行插入、删除元素等操作时，只需要修改指针，时间复杂度低。在数据量小的时候，建议使用链式存储结构顺序存储结构使用下标表示元素之间的逻辑关系，不额外增加存储空间。链式存储结构需要额外的存储空间存储指针信息。在数据量大的时候，建议使用顺序存储结构。
3.在以下流程框图（局部）中完成插入排序算法（设数据在r数组中，n为元素个数）；编程序实现对大量商品数据进行排序，并运行测试。
参考答案：
流程图：
程序：
r=[21,25,49,25,16,8]
i=1
while i<6:
temp=r[i]
j=i-1
while temp=0:
r[j+1]=r[j]
j=j-1
r[j+1]=temp
i=i+1
for e in r:
print(e)
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)(共39张PPT)
第一课时 尝试使用插入排序法实现商品销量排序
信息技术沪教版 选择性必修1
第五单元 排序与查找
项目八 模拟实现商品排序
——常用排序算法及其比较
一、新课导入
二、排序
三、插入排序
四、尝试使用插人排序法实现商品销最排序
五、课堂活动
一、新课导入
在日常生活中经常可以看到各种排行榜，如关注度排行榜、流行歌曲排行榜、球队实力排行榜、销量排行榜等。许多网络购物平台提供当月最畅销的商品排行。假如某店铺中某一种类商品只有 6件不同价格的商品，若采用人工排序，由于数据量小，简单目测一下就可以得出排序结果。
但实际上大部分情况下的排序数据可能会是成千上万条，因此，采用人工的方式会耗时多，且容易出错。若采用合理的数据结构和算法，编程实现后，系统便能对大量数据进行自动排序，省时省力，且只要程序正确，基本不会出错。
二、排序
将一组次序任意的数据元素转变为按其关键字（可以标识数据元素的某个数据项的值）递增（或递减）次序排列的过程，称为排序。
序号 商品名称 单价（元） 销量（件）
0 文具盒1 10 190
1 文具盒2 15 170
2 文具盒3 12 180
…… …… …… ……
N-1 文具盒N-1 13 205
选择排序
交换排序
插入排序
三、插入排序
小时候你一定玩过扑克牌，当你在整理那些乱序的牌的时候，你想到的第一种方法一定是将这些新摸到的牌插入到对应的位置，以此来达到手牌有序。
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。
核心概念
实现思路：
1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果符合条件（比前面的大或者小，自定义），则让他们交换位置。
2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前面的数据都是有序的。
3.重复步骤二，一直到数据全都排完。
实现思路：
实例：
让我们以数组为例，假设有下面的数组：
我们可以看到，前面3个元素已经有序，后面7个元素还是无序状态，这时候我们需要将第4个元素插入到相应的位置，这样有序序列就从3增加到4，无序序列就从7减小到6。
如果对于一个含有n个元素的完全无序的数组，我们可以把第一个元素视作有序，其余 n-1 个元素视为无序，因为只有一个元素的数组肯定是有序的，所以每次将无序序列的第n-1一个元素插入到相应位置后，问题的规模就减少1。如果我们重复 n-1 次，数组就从无序变为有序了。
实例：
最后我们用代码实现一下插入排序。
实例：
def insertion_sort(array):
for i in range(1, len(array)):
v = array[i]
j = i - 1
while j >= 0 and array[j] > v:
array[j+1] = array[j] # 用前一个元素覆盖当前元素
j = j - 1
array[j+1] = v # 循环结束后，将 v 插入到相应位置
return array
四、尝试使用插入排序法实现商品销最排序
若某家店铺某一类商品6个品种的月销量分别是21，25，49，25*，16，8，要对这些商品按销量进行排序，可采用顺序存储结构下的插入排序法，部分过程如图所示。
先将初始无序序列的6件商品销量数据存放在下标0~5某一数组中，然后将第一个商品销量数据21视作初始有序序列。将剩余的5件商品销量数据视作无序序列。接下来每次从无序序列中取第一个商品销量数据插入到有序序列的适当位置上。为了操作方便，插入的商品销量数据与有序序列中商品销量数据从后往前依次比较，一边比较一边将大的商晶销量数据往后移动，直至找到插入位置。
思考与讨论
1.商品除了可以按销量排序外，还可以按什么排序？
思考与讨论
2.生活中还有哪些排序的例子？
思考与讨论
2.生活中还有哪些排序的例子？
身高、年龄、体重等
五、课堂活动
1.参照上述步骤画出剩下的排序过程图。
2.若采用链式存储结构，请根据图所示，用文字描述排序过程，并画出每个过程图。谈谈使用顺序存储结构和链式存储结构实现插人排序，各有何特点，以及具体的算法是否相同；在数据量小和大的情况下分别用哪一种比较好。
插入排序过程(采用链式存储结构)：
(1)将原始链表断成有序链表和无序链表。有序链表包括头结点和第一个数据结点，指针Head指向头结点。无序链表包括第二个数据结点开始的所有结点，指针p指向第二个数据结点。
(2)通过指针P获得下一个需要排序数据25(无序链表的第一个节点)。在有序链表中查找第一个大于25的数据结点9,在结点之前插入结点25。若找不到大于25的数据节点，则将结点25插在有序链表的最后。结点25插入有序链表后，断开与无序链表的连接。指针指向无序链表的下一个结点49。
参考答案：
插入排序过程(采用链式存储结构)：
(3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下，
插入25:
参考答案：
插入排序过程(采用链式存储结构)：
(3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下，
插入49:
参考答案：
插入排序过程(采用链式存储结构)：
(3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下，
插入25*:
参考答案：
插入排序过程(采用链式存储结构)：
(3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下，
插入16:
参考答案：
插入排序过程(采用链式存储结构)：
(3)重复步骤(2)，将无序链表中的结点依次插入有序链表中插入过程示意围如下，
插入8:
参考答案：
顺序存储结构与链式存储结构的比較：
对于插入位置，顺序存储结构可以从有序序列的首部开始查找也可以从尾部开始查找。链式存储结构通过指针指向下一个结点，因而单链表只能从有序序列的首部开始查找
顺序存储结构在进行插入、删除元素等操作时，需要移动其他元素时间复杂度高。而链式存储结构在进行插入、删除元素等操作时，只需要修改指针，时间复杂度低。在数据量小的时候，建议使用链式存储结构顺序存储结构使用下标表示元素之间的逻辑关系，不额外增加存储空间。链式存储结构需要额外的存储空间存储指针信息。在数据量大的时候，建议使用顺序存储结构。
参考答案：
3.在以下流程框图（局部）中完成插入排序算法（设数据在r数组中，n为元素个数）；编程序实现对大量商品数据进行排序，并运行测试。
参考答案：
参考答案：
程序：
r=[21,25,49,25,16,8]
i=1
while i<6:
temp=r[i]
j=i-1
while temp=0:
r[j+1]=r[j]
j=j-1
r[j+1]=temp
i=i+1
for e in r:
print(e)
谢谢
21世纪教育网（www.21cnjy.com) 中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php
