基本演算法介紹-排序
選擇排序法 (Selection Sort)
圖片來源:https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
基本來說,選擇排序只需要重複執行兩個步驟,分別是:
(1)找最小(大)值
從「未排序好的數字」中找到最小(大)值
(2)丟到左邊
把最小值丟到「未排序好的數字」的最左邊,把它標示成已排序好
假設有一個 [41, 33, 17, 80, 61, 5, 55] 的陣列,我們用圖的例子來一步一步理解選擇排序是如何進行,在下面的圖中,我們把尚未排序好的數字用紅色標示,這輪找到的最小值以橘色標示,排序好的以藍色標示。
插入排序法 (Insertion Sort)
圖片來源:https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif?uselang=zh-hant
插入排序法 Insertion Sort 則是另外一個非常常見的排序法。簡單來說,插入排序法就是你玩撲克牌時用到的排序法。
(1)讀一個數字
從「未排序過的數字」中讀取一個數
(2)插入合適位置
把這個讀取的數往前插入一個位置
假設有一個 [41, 33, 17, 80, 61, 5, 55] 的陣列,在下面的圖中,我們把尚未排序過的數字用紅色標示,這輪要插入的值以橘色標示,排序過的以藍色標示。
牛刀小試1-排序RPG遊戲
遊戲開發:師大許庭嘉教授團隊
遊戲順序
選擇排序法 (Selection Sort)程式實作篇(老師可依學生程度實作.此為高一課綱)
Scratch實作選擇排序法 (Selection Sort)演算法(選授)
https://scratch.mit.edu/projects/180636046/
https://class.tn.edu.tw/modules/tad_web/news.php?WebID=1384&NewsID=9575
快速排序法(Quick sort)
https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
(1)選基準值(Pivot)
將比基準值(Pivot)小的數值移到基準值左邊,形成左子串列
將比基準值(Pivot)大的數值移到基準值右邊,形成右子串列
(2)分割(Partition)
將數列依基準值分成三部份(快速排序作法中,第2,3步驟)
左子數列:比基準值小的數值
中子數列:基準值
右子數列:比基準值大的數值
參考資料
http://peanut.lkjh.tyc.edu.tw/moodle/course/view.php?id=2
合併排序法(Merge sort)
https://www.udiprod.com/ms-vs-qs/
排序演算法評量
利用你所學的排序演算法排序容器的重量順序(升冪或降冪皆可)
(60s內完成.目前記錄31s)