資源簡介

(共22張PPT)
排序算法
信息科技-五下
小睿的學校正在舉行智力運動會，其中一項挑戰是:
有10個大小相似但質量不同的蘋果，參賽者可借助一架天平，將它們按照質量由小到大的順序排列，用的時間最少且方法最好的選手獲勝。
你會怎么做呢
按照質量給蘋果進行排序，就是一個不斷比較每兩個蘋果質量的過程。
在這個比較過程中，每個蘋果都要參與比較，但不同的排序算法會導致蘋果比較的次數有所不同。
選擇排序
選擇排序是一種簡單直觀的排序算法。它的原理是從序列頭部開始逐步構建有序序列，對于未排序數據，逐個選擇出其中最小者插入已排序序列的尾部。
使用選擇排序的方法對10個蘋果進行排序，每個編號位置放置一個蘋果
第一輪，找出10個蘋果中質量最輕的
第1步，使用天平比較0號和1號位置的蘋果。
如果0號位置的蘋果重則交換兩個蘋果的位置，否則不交換。
第2步，用第1步比較出質量輕的蘋果q分別與2-9號蘋果進行比較，如果重就交換，輕則不交換，即可找出質量最輕的蘋果，并把它放到首位。思考總共比較了_______次。
q
2
第二輪，找出 10個蘋果中第二輕的
第1步，用1號位置的蘋果，重復第一輪的步驟，選出第二輕的蘋果思考總共比較了_____次。
第2步，將第二輕的蘋果放置1號位置
將剩余的蘋果按照前面的方法全部排好序，
總共比較了你是怎樣計算的
假設 10 只蘋果的質量如表所示，思考如何補全程序，完成 10個蘋果的選擇排序程序。
選擇排序簡單直觀，占用計算機資源較少，適用于小數據量的排序任務它為需要簡單實現和調試的場景提供了便利。
冒泡排序
冒泡排序是一種簡單的排序算法，其重復訪問待排序數組，在一次訪問中，依次比較兩個相鄰元素，逆序時就交換，重復進行直到沒有交換為止在排序過程中，大的數據往下沉，小的數據往上浮，就像氣泡一樣，便將這種排序算法形象地稱為冒泡排序。
第一輪，找出10個蘋果中質量最重的一個
第1步，從0號位置的蘋果開始，0號與1號位置比較，如果0號位置的蘋果較重，則交換，否則不交換，比較_____次。
第2步，從1號蘋果開始重復第1步，分別與后面相鄰的蘋果比較，直到所有蘋果比較完成，總共比較_____次。
第二輪，找出第二重的蘋果。經過第一輪比較和排序，9號位置的革果已經是最重的了。第二輪中，繼續采用第一輪的方法，從0-8號位置中選出最重的蘋果，總共比較______次。
第三輪，重復第一輪的步驟，繼續進行排序，直至所有蘋果都完成3排序。最終，最輕的蘋果在0號位置，最重的蘋果在9號位置。
通過對比選擇排序和冒泡排序的執行次數，我們可以看出，這兩種算法都需要進行大量的數據比較，因此，它們的執行效率相對較低。
快速排序
快速排序是另外一種比較實用的排序方法，它通過一趟掃描將要排序的數據分割成獨立的兩部分，其中一部分的所有數據比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以將整個數據變成有序序列。
第一輪，選擇基準蘋果，并將其余的蘋果分成兩部分第1步，在10 個蘋果中選擇1個作為基準值。
第2步，分別用天平比較基準蘋果和其余的蘋果，將比基準值重的蘋果放在B組，將比基準值輕的蘋果放在A組。根據兩組的數量，即可確定基準蘋果的位置，共比較_____次。
第二輪，在A組中選擇一個蘋果作為基準值，在B組中選擇一個革果作為基準值，按照第一輪的方法再進行比較、分組，并確定基準蘋果位置，A組比較____次，B組比較____次。
第三輪，重復第一輪的步驟，直到將所有蘋果進行排序，總共比較____次。
快速排序因其實現簡單和適用性廣，在計算機科學和信息技術領域得到了廣泛應用。它在數據分析、信息檢索、圖像處理等各個領域發揮著重要作用。
1.分別將選擇排序、冒泡排序和快速排序三種不同的算法在解決蘋果排序問題時的比較次數，填寫在表中。
2.對比選擇排序、冒泡排序和快速排序，你認為哪一種算法效率最高 為什么
3.當需要排序的數據量較小時，可以選擇哪種算法 數據量較大時，又該選擇哪種算法
4.隨著互聯網、人工智能等領域的廣泛應用，排序算法獲得了更廣闊的應用空間。查閱相關資料，說一說除了選擇排序、冒泡排序、快速排序外還有哪些排序算法，以及它們應用的情境。
1、假設你有一堆卡片，想以最快的速度將它們由小到大排好。下列排序方法最快的一項是()
A.采用選擇排序方式，逐一查找，從小到大排列
B.采用冒泡排序方式，讓相鄰卡片依次比大小，大的沉底，小的上浮
C.采用快速排序方式，任選一張卡片作為參照，將卡片分成兩組，再對每一組重復相同的操作
D.將每張卡片試著放在各個位置，選擇最合適的位置
2、有10個大小不同的數字，分別為5、2、9、1、7、4、8、6、3、0.將這些數字按照從小到大的順序排列，你會用到哪幾種排序方法 你覺得哪種方法最適合 為什么
THANK YOU

展開更多......

收起↑