四川省教育科學研究院八年級上冊信息技術,第三單元:生活中的策略思維 第三節:常見的策略,NOW.,讓我先來cosplay一下 體育老師!,超級英雄排隊,超級英雄排隊,抽象為數字比較大小,第一趟,第二趟,第三趟,第四趟,第五趟,排序完成,WIFI信號滿格,策略,什么是策略?,策略 = 算法 = 解決問題的有限步驟的序列,程序 = 算法+數據結構 算法是程序的靈魂 -唐納德.克努斯,排序算法(Sorting algorithm),冒泡排序(Bubble Sort) 算法思想： 第一趟兩兩比較相鄰記錄,反序則交換,第一趟排序的結果可以將最大的元素,交換到最后的位置,固定住最大的元素. 第二趟兩兩比較相鄰記錄,反序則交換,第二趟排序的結果可以將第二大的元素,交換到最后的位置,固定住第二大的元素. .重復以上操作直到最小的元素被固定住,排序完成.,兩兩比較,反則交換,學生活動:,利用剛學的冒泡排序的方法再來一次排隊,冒泡排序效率分析,排隊主要的時間花在了什么地方呢?,交換,比較,衡量算法效率的標準 時間復雜度 空間復雜度,冒泡排序效率分析,如何提高排序的效率?,減少交換,減少比較,更快的排序方法快速排序(Quick Sort),算法思想: 1隨機選取一位同學作為基準值,所有比基準值矮的同學都站在他的左邊,所有比基準值高的同學都站在他的右邊,本輪被選為基準值的同學固定住位置,當前位置即為排序完成后的位置. 2對基準值左邊的同學應用以上策略. 3對基準值右邊的同學應用以上策略. 4直到被固定的同學的左右兩邊的人數之和小于2,排序完成,快速排序視頻演示,祖師爺和祖師奶奶,-,祖師奶奶教你用紙筆演練算法,兩兩比較 反則交換,紙筆演算視頻演示,題目,請將以下序列按從小到大的次序排列: 9 3 7 5 2,編程解決問題的一般步驟,明確輸入|輸出 抽象出數學模型 編寫算法 把算法利用一種計算機編程語言轉化為程序 測試及調試程序,直到程序能夠得到預期的結果為止,編程實現,編程實現,作業,查閱資料了解其他排序算法： 如 插入排序 選擇排序 希爾排序 堆排序 基數排序等 查閱資料了解其他算法思想： 如 貪心算法 枚舉算法 動態規劃算法等,thinks for watching