108課綱國中資訊科技人工智慧與演算課程設計

108課綱國中資訊科技人工智慧與演算法課程設計

更新時間:2021年4月12日

演算法基本介紹-排序

排序演算法(Sorting algorithm)

對雜亂無章的原始資料 ( Raw Data ) 進行整理、做排序的動作，在整個資訊科學或者電腦程式設計上都是十分重要的一件工作！

在資訊科學，排序演算法是一種能將一串資料依照特定排序方式進行排列的一種演算法。最常用到的排序方式是數值順序以及字典順序排序法，就是將一堆沒有排序過的數字由小到大（或大到小）排列好的演算法

資料引用:https://jason-chen-1992.weebly.com/home/-sorting-algorithm

已知的排序演算法超過幾十種，常見的排序演算法有:

氣泡排序法（Bubble sort）
選擇排序法（Selection sort）
插入排序法（Insertion sort）
合併排序法（Merge sort）
快速排序法（Quick sort）

活動

實作1-排序遊戲-天平遊戲

校內:http://10.231.114.1/luti/109-2-an/html5_sort_scale/sort_scale.html

http://163.22.72.196/html5/html5_sort_scale/sort_scale.html

遊戲玩法:

按下「開始」之後，利用畫面中央的天平，將畫面上八個瓶子按照重量大小順序排列，排列後按下「完成」，並檢查你的答案是否正確。對於順序的排列，如果有更好的方法，可以有效地減少完成所需的時間

解說1:

https://sites.google.com/ntjh.ntct.edu.tw/cstt/06-%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95

實作2-排序演算法視覺化操作

解說:

(1)氣泡排序法(Bubble Sort)

它演算法的想法是，從頭開始走訪我們要進行排序的數列，然後每次比較數列中相鄰的兩個元素，如果他們大小順序錯誤的話就讓他們互換，如此重複到再也沒有需要交換，即代表排序完成。演算流程如下圖

你可以看到，其中比較大or比較小 ( 取決於你要從小排到大；還是從大排到小 ) 的元素會被慢慢換到數列的最前面，這個過程就像水中的小泡泡慢慢浮上水面一樣，所以叫Bubble Sort。

資料引用:https://jason-chen-1992.weebly.com/home/-sorting-algorithm

(2)選擇排序法 (Selection Sort)

選擇排序可以說是最簡單、最直觀的排序演算法了，它演算法的概念很簡單，一個一個檢查未排序的資料，找最小(或最大)的從頭開始排，如此重複執行到結束。

圖片來源:https://jason-chen-1992.weebly.com/home/selection-merge-heap

基本來說，選擇排序只需要重複執行兩個步驟，分別是：

(1)找最小(大)值

從「未排序好的數字」中找到最小(大)值

(2)丟到左邊

把最小(大)值丟到「未排序好的數字」的最左邊，把它標示成已排序好

假設有一個 [41, 33, 17, 80, 61, 5, 55] 的陣列，我們用圖的例子來一步一步理解選擇排序是如何進行，在下面的圖中，我們把尚未排序好的數字用紅色標示，這輪找到的最小值以橘色標示，排序好的以藍色標示。

(3)插入排序法 (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] 的陣列，在下面的圖中，我們把尚未排序過的數字用紅色標示，這輪要插入的值以橘色標示，排序過的以藍色標示。

(4)快速排序法(Quick sort)

Quick Sort採用了分治法(Divide and conquer)，其的精神就是，分而治之、各個擊破！

基於這個策略，Quick Sort 會將要進行排序的序列( list ) 分割成兩個子序列( sub-list )，步驟為：

1.從數列中挑選出一個元素( Element ) 作為基準( Pivot )。

2.重新排序數列，所有小於 Pivot 的元素擺放在 Pivot 前面，所有大於 Pivot 的元素擺在 Pivot 後面。

至於等於 Pivot 可任意的擺在在其中一邊，到此為止的步驟可以稱做規劃或分割( Partition )。