基本演算法介紹-排序

合併排序法 (Merge Sort)

合併排序法(Merge Sort) 相對於選擇排序法，合併排序法屬於比較進階的演算法，排序方法也比較複雜一點，基本的步驟可以分為「拆分」與「合併」：

拆分

把大陣列切一半成為兩個小陣列.

把切好的兩個小陣列再各自切一半 重複步驟二直到每個小陣列都只剩一個元素

合併

排序兩個只剩一個元素的小陣列並合併

把兩邊排序好的小陣列合併並排序成一個陣列

重複步驟二直到所有小陣列都合併成一個大陣列

插入排序法 Insertion Sort 則是另外一個非常常見的排序法。簡單來說，插入排序法就是你玩撲克牌時用到的排序法。

讀一個數字

從「未排序過的數字」中讀取一個數

插入合適位置

把這個讀取的數往前插入一個位置

A.圖解

圖片來源:https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif?uselang=zh-hant

現在，讓我們再次出動熟悉的數列 [41, 33, 17, 80, 61, 5, 55] 當作例子來說明：
在圖中的上半部，我們將未排序的陣列對半切，直到每個小陣列都只剩一個元素；而在圖中的下半部，我們將被對半切開的小陣列兩兩合併與排序。
因為兩個小陣列在合併前都各自排序好了（只有一個元素的陣列也視為已排序），所以在合併兩個排序好的陣列時，我們只需要不斷比較兩邊的第一個元素，把比較小的丟到新的大陣列，就能完成排序。

B.影片

活動設計1-合併排序(Merge sort)演算法視覺工具

快速排序(Quick sort)

快速排序法是排序演算法的一種，快速排序是一種“把大問題分成小問題處理”的分而治之方法

A.圖解

B.影片

活動設計2-快速排序(Quick sort)演算法視覺工具

活動設計3-排序概念操作動畫以天平找出容器的重量順序

參考網站

• https://kknews.cc/news/k89raoq.html
• http://visualgo.net/
• http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
• http://iguang.tw/u/4199891/article/137341.html

活動設計4-以程式語言Python實作排序概念

排序法

步驟:

1.進入線上Python編譯器

2.將預設的內容刪除

3.將Python程式語言以下語法貼到線上編譯器

def sort(nb1, nb2):
    if len(nb1) == 0: return nb2
    elif len(nb2) == 0: return nb1
    elif nb1[0] < nb2[0]: return [nb1[0]] + sort(nb1[1:], nb2)
    else: return [nb2[0]] + sort(nb1, nb2[1:])
    
number1 = [4,13,6,6,2,7,2,9,29]
number2 = [4,13,6,6,2,7,2,9,29]
number1.sort()
number2.sort()
print(sort(number1, number2))

4.貼到編譯器

5.點執行(Run)

6.觀看執行結果

7.試著修改程式碼再執行看看