資源簡介

(共30張PPT)
魚吐泡泡
粵教版選擇性必修一
——冒泡排序
回顧：認識排序
排序是把一個任意序列的數據元素排列成按照某關鍵字的一個有序序列的過程
游戲：探究人如何實現排序
四位同學，隨意排好順序，從第一位同學開始往后排序，每位同學只能和后面一位同學交換位置，最終按學號從小到大的順序排列。
如何一步步實現排序
什么時候結束排序
游戲：探究人如何實現排序
相鄰比較
逆序交換
VS
冒泡排序
多輪排序
數列有序
核心步驟
魚吐泡泡
冒泡排序過程就像魚在水里冒泡的過程，小泡泡在下面，大泡泡在上面
2
5
9
1
3
5
3
2
9
1
魚吐泡泡
冒泡排序是交換排序算法。依次進行大小比較來交換相鄰兩個逆序數據元素，冒泡排序中每一輪會確定一個數據的位置，逐步將待排序列變成有序序列。
任務一：人工進行學號的冒泡排序
在學習單上嘗試人工解決排序問題，得到答案
時間：3分鐘
3
5
2
6
8
排序過程
初始 6 3 8 5 2
第1遍
第2遍
第3遍
第4遍
3 5 2 6 8
3 2 5 6 8
3 6 5 2 8
2 3 5 6 8
相鄰元素比較、逆序交換
多輪排序
從第一個元素到最后一個元素
冒泡排序基本思想
初始 6 3 8 5 2
第1遍
第2遍
第3遍
第4遍
1.假設有n個待排序元素，從第一個元素開始，相鄰兩個元素進行大小比較，根據結果交換位置，第一輪排序結束后最大的元素會移動到末尾。
2.按照上述方法進行第二輪排序，第二大的元素會移動到倒數第二個位置。
3. 經過n-1輪排序后，整個序列就是一個有序序列
3 6 5 2 8
3 5 2 6 8
3 2 5 6 8
2 3 5 6 8
冒泡排序
如果待排序的數據量達到上萬、上百萬，甚至更大，如何快速地利用冒泡排序來解決問題
人工排序
電腦排序
冒泡排序算法+計算機
冒泡排序算法分析
相鄰元素比較、逆序交換
從第一個元素到最后一個元素
多輪排序
分支結構
循環結構
循環結構
算法：
循環列舉第一個元素到最后一個元素：
循環進行下列步驟：
直到所有元素有序排列，程序結束
如果相鄰兩個元素滿足大小條件：
交換相鄰兩個逆序元素的位置
流程圖
開始
r[0]>r[1]
r[0]和r[1]交換位置
Y
N
j=j+1
j=0
r[3]>r[4]
r[3]和r[4]交換位置
Y
N
·····
開始
j=0
jr[j]和r[j+1]交換位置
Y
j=j+1
Y
r[j]>r[j+1]
N
結束
N
結束
流程圖
開始
r[j]>r[j+1]
i=0
r[j]和r[j+1]交換位置
Y
N
j=j+1
jj=0
Y
i=1
·····
開始
結束
r[j]>r[j+1]
i=0
r[j]和r[j+1]交換位置
Y
N
j=j+1
ijj=0
Y
Y
i=i+1
N
N
N
流程圖
開始
結束
r[j]>r[j+1]
i=0
r[j]和r[j+1]交換位置
Y
N
j=j+1
ijj=0
Y
Y
i=i+1
N
N
多輪排序
每一輪排序
相鄰比較、逆序交換
任務二：學號冒泡排序的代碼實現與優化
基礎任務：打開學號冒泡排序程序框架，完善核心部分
選做的進階任務：自學拓展資料，完善學號冒泡排序優化代碼的核心部分
時間：6分鐘
任務二：學號冒泡排序的代碼實現與優化
基礎任務代碼
進階任務代碼
冒泡排序解決問題的一般步驟
分析問題
設計算法
確定排序對象
確定交換條件
排序結束條件
循環與分支結構
程序實現
運行程序
編寫代碼
得到有序序列
任務二
結合學習單上的問題二，完成基礎任務，選做進階任務
小組討論
任務二：考試分數排序的代碼實現與優化
基礎任務：打開學號冒泡排序程序框架，完成考試分數排序的代碼實現
選做的進階任務：自學拓展資料，完善考試分數冒泡排序優化代碼的核心部分
時間：6分鐘
程序對比
冒泡排序算法優化
一輪排序后沒有發生交換則結束程序
上一輪最后發生交換的位置之前不再發生交換則結束程序
冒泡排序進一步優化
冒泡排序優化
任務三：考試分數排名的代碼優化
要求：結合剛才的分析，完成程序再優化
時間：3分鐘
任務三：考試分數排名的代碼優化
冒泡排序算法優化小結
冒泡排序優化方法一：
一輪排序后沒有發生交換則結束
冒泡排序優化方法二：
上一輪發生交換的位置之前不再發生交換則結束
交流與評價
現在整理自己之前編寫的程序放到共享區域，在共享區域查看他人編寫的冒泡排序程序并相互交流討論，學習他人作品的優點。填寫學習單上的自評與互評，進行反思總結。
課堂總結
相鄰元素兩兩比較、逆序交換、多輪排序
每輪排序過程中，值小的元素向前移動，值大的元素向后移動
冒泡排序算法：雙層循環與分支的嵌套
冒泡算法的課后作業
完成學習單上的課后作業
課堂效果調查
https://www./vm/Y0nv3aQ.aspx#
謝 謝

展開更多......

收起↑