資源簡介

第二課：排序算法
教學內容：
本課程以蘋果排序為情境，引導學生探究選擇排序、冒泡排序和快速排序等經典排序算法。在探討這三種排序方法原理的過程中，學生將運用分解、抽象、建模等計算思維技巧，了解每種排序算法的基本特征，并使用圖形化編程軟件編寫程序來體驗算法的運行過程。
教學目標：
知道排序算法的含義，熟練掌握三種排序算法的原理，
2.能知道不同排序算法的效率，能根據實際情況選擇合適的排序算法
教學重點：
(1)排序算法的含義。
(2)三種算法的應用。
教學難點：
三種算法的應用。
教學過程：
情境導入
師:學校正在舉行智力運動會，其中一項挑戰是：（看大屏幕）有10個大小相似但質量不同的蘋果，參賽者可借助一架天平，將它們按照質量由小到大的順序排列，用的時間最少且方法最好的選手獲勝。你會怎么做呢
生: ......
師:按照質量給蘋果進行排序，就是一個不斷比較每兩個蘋果質量的過程。在這個比較過程中，每個蘋果都要參與比較，但不同的排序算法會導致蘋果比較的次數有所不同。
師:選擇排序是一種簡單直觀的排序算法。它的原理是從序列頭部開始逐步構建有序序列，對于未排序數據，逐個選擇出其中最小者插入已排序序列的尾部。
教學過程：
選擇排序
師:接下來我們使用選擇排序的方法對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組比較____次。
第三輪，重復第一輪的步驟，直到將所有蘋果進行排序，總共比較____次。
4、排序算法的比較
師：請根據前三個小試身手的內容，分別將選擇排序、冒泡排序和快速排序三種不同的算法在解決蘋果排序問題時的比較次數，填寫在表中。
生：
總結
排序算法廣泛應用于多個領域，例如數據庫查詢中用于快速定位所需數據;搜索引擎中確保搜索結果按相關性排序;數據分析中幫助識別數據模式和趨勢。此外，排序算法還在圖像處理、網絡安全、電子商務等領域發揮重要作用。如快速排序、歸并排序和堆排序更為合適。此外，優化策略如改進基準元素的選擇減少不必要的比較和交換操作，也能提高排序效率。好了，今天的課就上到這里了，接下來有兩個習題大家可以做一下，檢驗一下自己本節課的學習成果吧。
挑戰自我
課后習題
1、假設你有一堆卡片，想以最快的速度將它們由小到大排好。下列排序方法最快的一項是()
A.采用選擇排序方式，逐一查找，從小到大排列
B.采用冒泡排序方式，讓相鄰卡片依次比大小，大的沉底，小的上浮
C.采用快速排序方式，任選一張卡片作為參照，將卡片分成兩組，再對每一組重復相同的操作
D.將每張卡片試著放在各個位置，選擇最合適的位置
2、有10個大小不同的數字，分別為5、2、9、1、7、4、8、6、3、0.將這些數字按照從小到大的順序排列，你會用到哪幾種排序方法 你覺得哪種方法最適合 為什么

展開更多......

收起↑