资源简介

(共31张PPT)
3.2数据的排序
高中信息技术/教科版/选择性必修1
目录
1.情境导入
3.讨论探究
2.体验探究
4.课堂小结
1.情境导入
网上商城平台是如何实现按价格、销量等进行升序或降序排序，并显示商品信息的呢
本节围绕“按序查看商品”项目展开学习，通过项目活动学习常见的排序算法，体会迭代方法的具体应用，理解数据结构与算法的关系。本节主要包含 “按价格升序显示商品”和“按销量降序显示商两个任务。
2.体验探究
任务一 按价格升序显示商品 活动1初步尝试排序
下面是某网上商城的签字笔销售数据，请将表中数据按价格从低到高进行排序，将排序后的结果填入对应的表格中。
品牌 销量/盒 价格/元 评论数/条
博士 80 66 108
英雄 188 78 86
永辉 236 58 186
晨辉 200 46 190
得利 56 68 50
梅花 185 26 92
签字笔销售数据
任务一 按价格升序显示商品 活动1初步尝试排序
品牌 销量/盒 价格/元 评论数/条
填一填
按价格从低到高排序后的签字笔销售数据
梅花 185 26 92
晨辉 200 46 190
永辉 236 58 186
博士 80 66 108
得利 56 68 50
英雄 188 78 86
你是如何排序的呢？
对签字笔销售数据按照价格从低到高进行排序的过程就是整理数据顺序的过程。通过比较价格的大小，调整数据的顺序。在整理的过程中，只调整数据的排列顺序，不改变数据内容。
排序(sorting)就是整理数据的顺序，使其从无序变为有序。
排序的概念
3.讨论探究
任务一 按价格升序显示商品 活动2体验冒泡排序过程
博士
66
英雄
78
永辉58
晨辉46
得利68
梅花26
不交换
博士
66
英雄
78
永辉58
晨辉46
得利68
梅花26
交换
博士
66
永辉58
晨辉46
英雄78
得利68
梅花26
交换
博士
66
永辉58
晨辉46
得利68
英雄78
梅花26
博士
66
永辉58
晨辉46
得利68
梅花26
英雄78
交换
交换
在未排序的签字笔销售数据中找到价格最高者放在序列的末尾，这样未排序的签字笔销售数据就会减少1个。若干次迭代后，当未排序的签字笔销售数据只剩下一个时，排序就完成了。
第1次迭代过程
任务一 按价格升序显示商品 活动2体验冒泡排序过程
经过5次“比较一交换”，第1次迭代后价格的序列是: 66,58，46，68，26，78。根据这个思路，补全图3.2.3，完成第2次迭代过程。
博士
66
永辉58
晨辉46
得利68
梅花26
英雄78
英雄78
英雄78
英雄78
交换
永辉
58
晨辉46
博士66
得利
68
梅花26
永辉
58
晨辉46
博士
66
得利
68
梅花26
永辉
58
晨辉46
博士
66
梅花26
得利
68
交换
不交换
交换
第
2
次
迭
代
过
程
任务一 按价格升序显示商品 活动2体验冒泡排序过程
填一填
第 2次迭代后价格的序列是: ，
未排序的数据剩下 个。
第 3次选代后价格的序列是: ，
未排序的数据剩下 个。
第 4 次迭代后价格的序列是: ,
未排序的数据剩下 个。
第 5次选代后价格的序列是: ,
未排序的数据剩下 个。
经过5次迭代，最后完成了6个签字笔销售数据按照价格升序排列。
58，46，66，26，68，78
4
46，58，26，66，68，78
3
46，26，58，66，68，78
2
26，46，58，66，68，78
1
任务一 按价格升序显示商品 活动3建立数据结构
冒泡排序(bubble sort) 是一种通过“比较一交换”进行排序的方法，首先将第1个数据和第2个数据进行比较，若为逆序，则将两个数据交换位置;然后比较第2个数据和第3个数据，以此类推，直至最后两个数据进行过“比较一交换”为止。上述过程称作第一趟“冒泡”，其结果使得最大的数据被放到最后的位置上。之后对除了最大数据之外的剩余部分进行下一趟“冒泡”，经过若干趟“冒泡”后，如果剩余部分只包含一个数据，则冒泡排序完成。
冒泡排序
任务一 按价格升序显示商品 活动3建立数据结构
为了便于对签字笔销售数据进行处理，定义签字笔商品类，其Python代码如下。
01.#定义签字笔商品类
02. class pen:
03.def __init__(self, brand, sales, price, comments)
04.self.brand=brand #品牌
05.self.sales=sales #销量
06.self.price=price #价格
07.ments=comments #评论数
任务一 按价格升序显示商品 活动3建立数据结构
创建一个线性表对象alist，存放表3.2.1所示的签字笔销售数据对象。请补全下面的代码。
08.from linearList import LinearList #导入线性表
09.alist=LinearList() #创建线性表对象"
10.alist.appendItem(pen("博士",8,66,108)) #添加签字笔数据元素
11.alist.appendItem(pen("英雄",188,78,86)) #添加签字笔数据元素
12.alist.appendItem(pen("永辉",236,58,186)) #添加签字笔数据元素
13alist.appendItem(pen( ))#添加签字笔数据元素
14.alist.appendItem(pen( ))#添加签字笔数据元素
15.alist.appendItem(pen( )) #添加签字笔数据元素
‘晨辉’,200,46,190
‘得利’,56,68,50
‘梅花’,185,26,92
任务一 按价格升序显示商品 活动4算法设计与实现
假设有n个签字笔销售数据，冒泡排序的算法描述如下：
(1)进行n-1趟“冒泡”过程，每趟操作如步骤(2)和(3)，如果未完成则继续进行操作。第1趟的冒泡范围是n个数据
(2)从第1个数据开始，依次比较相邻两个数据，如果逆序则交换位置，直到比较完最后两个数。冒泡范围内的最大数据会被交换到最后的位置上。
(3)将本趟的最大数据排除出“冒泡”操作范围。
根据上述算法，定义冒泡排序函数bubbleSort(alist,key)，参数alist表示需要排序的线性表，key表示排序的关键词。请补全下面的代码。
任务一 按价格升序显示商品 活动4算法设计与实现
16.#冒泡排序算法
17. def bubbleSort(alist， key):
18.for i in range(alist.size()-1): #控制“冒泡”趟数
19.#控制“冒泡”范围
20.for j in range(1,alist.size()-i):
21.#相邻两数比较
22.if getattr( , key) > getattr(alist.getItem(j), key):
23.temp=alist.getItem(j-1)
24.alist.setItem(j-1, alist.getItem(j))
25.alist.setItem(j, ） #交换位置
alist.getItem(j-1)
temp
任务二 按销量降序显示商品 活动1体验直接插入排序过程
如何将表中的所有数据按照销量从高到低进行排序呢
第1个签字笔销售数据已经有序，把待排序的签字笔销售数据按照销量插入到有序序列的合适位置，有序数据就增加1个。这样迭代若干次后，直到所有的待排序签字笔销售数据插入完为止，排序就完成了。
比较插入
任务二 按销量降序显示商品 活动1体验直接插入排序过程
销量是80的签字笔销售数据是有序子序列，把销量为188的签字笔销售数据插入。
比较80和188的大小，80<188，将销量为80的签字笔销售数据后移一个位置，将销量为188的签字笔销售数据插入到它的前面。
第1次迭代后销量的序列是: 188，80，236，200，56，185。
第1次迭代
任务二 按销量降序显示商品 活动1体验直接插入排序过程
第2次迭代: 插入销量为236的签字笔销售数据，从有序子序列(188,80)的最后1个数据开始，将销量为236的签字笔销售数据与序列中的数据逐一比较大小，确定插入位置。
比较80和236，80<236。将销量为80的签字笔销售数据后移一个位置；
比较188和236。188<236，将销量为188的签字笔销售数据后移一个位置，将销量为236的签字笔销售数据插入到它的前面。
经过两次比较后确定位置并插入，第2次迭代后销量的序列是: 236，188，80，200，56，185。
第2次迭代
任务二 按销量降序显示商品 活动1体验直接插入排序过程
请在下面的横线上依次写出其他各次迭代的结果。
第3次迭代: ：插入 ，
迭代后销量的序列是: ；
第4次迭代:插入 ，
迭代后销量的序列是: ；
第5次迭代:插入 ，
迭代后销量的序列是: ；
经过5次迭代，最后完成了6个签字笔销售数据按照销量降序排列。
填一填
200
236，200，188，80，56，185
56
236，200，188，80，56，185
185
236，200，188，185，80，56
任务二 按销量降序显示商品 活动1体验直接插入排序过程
直接插入排序(straight insertion sort)是一种通过“比较一插入进行排序的方法。基本操作是从有序子序列的最后一个数据开始，待排序的数据与有序子序列中的所有数据逐一进行比较，确定插入的位置并插入数据。上述过程称作一次插入操作，其结果是将一个数据插入到已经排好序的数据序列中，从而得到一个新的、数据数量增加一个的有序子序列。对未排序的数据进行相同的操作，重复若干次插入操作，直到所有的未排序数据插入完为止，则插入排序完成。
直接插入排序
任务二 按销量降序显示商品 活动2直接插入排序算法的设计与实现
分析活动1中排序过程和直接插入排序的基本思想，假设有n个签字笔销售数据，实现直接插入排序的算法描述如下：
(1) 进行n-1次插入操作，每次操作如步骤 (2)和(3)，如果未完成则继续进行。默认第1个数据是有序子序列。
(2) 取得当前待排序数据，从有序数据序列的最后一个数据开始，待排序数据与其逐一进行比较，如果大于对方则后移该数据，确定插入位置。
(3) 将待排序数据插入到有序数据序列中。
任务二 按销量降序显示商品 活动2直接插入排序算法的设计与实现
根据上述算法，定义insertionSort(alist,key)函数，参数alist表示要排序的线性表，key表示排序的关键词。请补全下面的代码。
16.#直接插入排序算法
17. def insertionSort(alist， key):
18.#默认第1个数据已有序，控制插入次数
19.for i in range(1,alist.size()):
20.currentdata =alist.getItem(i) #取当前待排序数据
21.j=i
22.#与待排序数据进行比较
任务二 按销量降序显示商品 活动2直接插入排序算法的设计与实现
23.while j> and getattr(alist.getItem(j-1),key)<
24.getattr( ）
25.alist.setItem(j,alist.getItem(j-1)) #后移数据
26.j=j-1 #确定插入位置
27.alist.setItem(j, ）#插入数据
currentdata，key
currentdata
任务二 按销量降序显示商品 活动2直接插入排序算法的设计与实现
以表中的数据为例，利用直接插入排序法实现签字笔销售数据按销量降序排序，并显示排序后的结果。请补全下面的代码。
28.insertionSort(alist, ）#调用直接插入排序法函数
29.print("按销量降序排序后的结果是:“)
30. for i in range(alist.size()):
31.#显示排序后的结果
32.print(getattr(alist.getItem(i),'brand'), ，
， ))
‘sales’
getattr(alist.getItem(i),'sales'
getattr(alist.getItem(i),'price'
getattr(alist.getItem(i),'comments'
4.课堂小结
对数据进行排序不只有冒泡排序法和直接插入排序法这两种排序算法，每种排序算法有不同的适用范围和针对的应用情境。在冒泡排序的过程中，数据的处理是基于数据的交换，直接插入法排序的过程则是数据的后移。
请同学们认真完成教材中的拓展练习哦！
下节课见！

展开更多......

收起↑