資源簡介

(共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.課堂小結
對數據進行排序不只有冒泡排序法和直接插入排序法這兩種排序算法，每種排序算法有不同的適用范圍和針對的應用情境。在冒泡排序的過程中，數據的處理是基于數據的交換，直接插入法排序的過程則是數據的后移。
請同學們認真完成教材中的拓展練習哦！
下節課見！

展開更多......

收起↑