此網頁內容為旗標科技公司出版的「會動的演算法」書中演算法動畫列表。在電腦上觀看時，請用滑鼠點選各個演算法對應的 QR Code 圖示；使用手機觀看時，請開啟手機內建的相機 App，或是開啟掃描 QR Code 的 App，即可觀看演算法逐步執行的動畫，建議搭配書中的說明，學習效果會更好喔！

本書出版前已力求內容的正確性，但相關內容也許在您閱讀時已有更新，作者會不定期更新書中的錯誤，您可以連到勘誤表查詢，中文版書籍已更新 2021 年以前的所有錯誤！若有本書的任何問題可 E-mail 給作者 (渡部有隆)。

Part 1 準備篇

第 3 章　演算法的基礎概念

常數 常數
對數 對數
線性 線性
線性、對數 線性、對數
二次函數 二次函數
三次函數 三次函數

Part 2 空間結構

第4～9章　

單節點 單節點
一維陣列 一維陣列
二維陣列 二維陣列
二元樹 二元樹
接近完整二元樹 接近完整二元樹
完整二元樹 完整二元樹
無向圖 無向圖
有向圖 有向圖
森林 森林
二維點群 二維點群
鏈結串列 鏈結串列
動態二元樹 動態二元樹

Part 3 演算法與資料結構

第 10 章 入門


2021/05/10
互換 (Swap)
互換 (Swap)
交換 2 個變數的值。
互換 | 輸入 互換 | 輸出
演算法動畫
2021/05/10
最大値 (Max)
最大值 (Max)
從 2 個數值中選出較大者。
最大值 | 輸入 最大值 | 輸出
演算法動畫
2021/05/10
利用互換做排序
利用互換做排序
請將 3 個整數依升冪 (由小至大) 排列。
互換排序 | 輸入 互換排序 | 輸出
演算法動畫

第 11 章 陣列基本查詢


2021/05/10
合計
合計（sum）
想計算 N 個整數的總和。
合計 | 輸入 合計 | 輸出
演算法動畫
2021/05/10
最小元素值
最小元素值
從 N 個整數中找出最小值。
最小元素值 | 輸入 最小元素值 | 輸出
演算法動畫
2021/05/10
最小元素值位置
最小元素值位置
從 N 個整數中找出最小元素的「位置」。
最小元素值位置 | 輸入 最小元素值位置 | 輸出
演算法動畫

第 12 章 搜尋


2021/05/10
線性搜尋法 (Linear Search)
線性搜尋法 (Linear Search)
請在陣列中尋找指定值。若指定值不存在，請傳回不存在；若存在，請傳回其最先出現的位置。
線性搜尋法 | 輸入 線性搜尋法 | 輸出
演算法動畫
2021/05/10
二元搜尋法 (Binary Search)
二元搜尋法 (Binary Search)
在升冪（由小到大）排序的陣列中尋找指定值。若指定值不存在，請傳回不存在；若指定值存在，則傳回其位置。。
二元搜尋法 | 輸入 二元搜尋法 | 輸出
演算法動畫

第 13 章 陣列元素排序


2021/05/10
反轉 (Reverse)
反轉 (Reverse)
將整數序列中的元素以反序排列。
反轉 | 輸入 反轉 | 輸出
演算法動畫
2021/05/10
插入
插入 (Insertion)
在升冪排序的序列中新增 1 個元素，並維持序列的升冪
狀態。
插入 | 輸入 插入 | 輸出
演算法動畫
2021/05/10
合併 (Merge)
合併 (Merge)
將 2 個升冪排列的序列，合併成 1 個依升冪排列的序列。
合併 | 輸入 合併 | 輸出
演算法動畫
2021/05/10
分割 (Partition)
分割 (Partition)
從序列中挑選 1 個適當的元素做為基準，將序列分成比基準小和比基準大的 2 個群組。
分割 | 輸入 分割 | 輸出
演算法動畫

第 14 章 必學的排序法


2021/05/10
氣泡排序法 (Bubble Sort)
氣泡排序法 (Bubble Sort)
請將整數序列{a0, a1, ..., aN-1}按照升冪排列。
氣泡排序法 | 輸入 氣泡排序法 | 輸出
演算法動畫
2021/05/10
選擇排序法 (Selection Sort)
選擇排序法 (Selection Sort)
請將整數序列{a0, a1, ..., aN-1}按照升冪排列。
選擇排序法 | 輸入 選擇排序法 | 輸出
演算法動畫
2021/05/10
插入排序法 (Insertion Sort)
插入排序法 (Insertion Sort)
請將整數序列{a0, a1, ..., aN-1}按照升冪排列。
插入排序法 | 輸入 插入排序法 | 輸出
演算法動畫
※ 此演算法不包含在書本裡 (補充教材)。2021/05/11
Shaker Sort(篩動排序法)
Shaker Sort (篩動排序法)
請將整數序列{a0, a1, ..., aN-1}按照升冪排列。
篩動排序法 | 輸入 篩動排序法 | 輸出
演算法動畫

第 15 章 與整數相關的演算法


2021/05/11
埃拉托斯特尼篩法 (Sieve of Eratosthenes)
埃拉托斯特尼篩法 (Sieve of Eratosthenes)
請建立 1 個質數表，其中第 i 個元素在整數 i 為質數時為 1，合數時為 0。
埃拉托斯特尼篩法 | 輸入 埃拉托斯特尼篩法 | 輸出
演算法動畫
2021/05/11
輾轉相除法 (Euclidean Algorithm)
輾轉相除法 (Euclidean Algorithm)
請求出 2 個整數的最大公因數。
輾轉相除法 | 輸入 輾轉相除法 | 輸出
演算法動畫

第 16 章 基本資料結構 1


2021/05/23
堆疊 (Stack)
堆疊 (Stack)
請實作一個採取後進先出（LIFO）原則，優先取出最後插入資料的資料結構。
堆疊 | 輸入
堆疊 | 輸出
演算法動畫
2021/05/23
佇列 (Queue)
佇列 (Queue)
請實作一個採取先進先出（FIFO）原則，優先取出最早插入資料的資料結構。
佇列 | 輸入
佇列 | 輸出
演算法動畫

第 17 章 陣列的計算


2021/05/16
累積和 (Accumulation)
累積和 (Accumulation) 的概念
從整數序列的一或多個區間，求出各區間的區間和。
累積和 | 輸入 累積和 | 輸出
演算法動畫
2021/05/16
一維累積和
一維累積和的應用
請從多條線段，求出各整數 x 座標上的重疊線段數量。
一維累積和 | 輸入 一維累積和 | 輸出
演算法動畫
2021/05/22
二維累積和
二維累積和的應用
從多個矩形求出各座標上重疊（1 個以上）的矩形數量。
二維累積和 | 輸入 二維累積和 | 輸出
演算法動畫
※ 此演算法不包含在書本裡 (補充教材)。2021/05/22
網格上的動態規劃法 (Dynamic Programming)
網格上的動態規劃法 (Dynamic Programming)
請從網格狀的道路圖中，求出從西北邊十字路口到東南邊十字路口的最短路徑數量，施工中的十字路口不能通過。
網格上的最短路徑數 | 輸入 網格上的最短路徑數 | 輸出
演算法動畫

第 18 章 堆積 (Heap)


2021/05/22
Up Heap
Up Heap
變更最大堆積其中 1 個節點的值（值變大），並依最大堆積的特性，重新調整堆積。
Up Heap | 輸入 Up Heap | 輸出
演算法動畫
2021/05/22
Down Heap
Down Heap
變更最大堆積其中 1 個節點值 (使其值變小)，並依最大堆積特性 (所有父節點值都大於子節點值)，重新調整堆積。
Down Heap | 輸入 Down Heap | 輸出
演算法動畫
2021/05/22
建立堆積 (Building Heap)
建立堆積 (Building Heap)
將整數序列建立成最大堆積。
建立堆積 | 輸入 建立堆積 | 輸出
演算法動畫
2021/05/23
優先佇列 (Priority Queue)
優先佇列 (Priority Queue)
請實作一個會優先取出優先權最高的資料 (本節以最大值為例) 的資料結構。
優先佇列 | 輸入
優先佇列 | 輸出
演算法動畫

基本資料結構：比較表

資料結構 時間複雜度 原則 技巧
堆疊 堆疊 常數 後進先出 (LIFO：Last-In-First-Out)
佇列 佇列 常數 先進先出 (FIFO：First-In-First-Out)
優先佇列 優先佇列 常數 優先取出優先權高者 heap

第 19 章 二元樹的走訪


2021/05/30
前序走訪 (Pre-order Traversal)
前序走訪 (Pre-order Traversal)
前序走訪：先走訪父節點再走訪子節點。
前序走訪 | 輸入 前序走訪 | 輸出
演算法動畫
2021/05/30
後序走訪 (Post-order Traversal)
後序走訪 (Post-order Traversal)
後序走訪：先走訪子節點再走訪父節點。
後序走訪 | 輸入 後序走訪回 | 輸出
演算法動畫
2021/05/30
中序走訪 (In-order Traversal)
中序走訪 (In-order Traversal)
中序走訪：先走訪完左子樹的所有節點，再走訪根節點，最後再走訪右子樹的所有節點。
中序走訪 | 輸入 中序走訪 | 輸出
演算法動畫
2021/05/30
層序走訪 (Level-order Traversal)
層序走訪 (Level-order Traversal)
層序走訪：先走訪完所有深度為 k-1 的節點，再走訪深度為 k 的節點。
層序走訪 | 輸入 層序走訪 | 輸出
演算法動畫

第 20 章 高效率的排序法


2021/05/15
合併排序法 (Merge Sort)
合併排序法 (Merge Sort)
請由小到大重新排列整數序列{a0, a1, ..., aN-1}。
合併排序法 | 輸入 合併排序法 | 輸出
演算法動畫
2021/05/15
快速排序法 (Quick Sort)
快速排序法 (Quick Sort)
請由小到大重新排列整數序列 {a0, a1, ..., aN-1}。
快速排序法 | 輸入 快速排序法 | 輸出
演算法動畫
2021/05/22
堆積排序法 (Heap Sort)
堆積排序法 (Heap Sort)
請由小到大重新排列整數序列{a0, a1, ..., aN-1}。
堆積排序法 | 輸入 堆積排序法 | 輸出
演算法動畫
2021/05/15
計數排序法 (Counting Sort)
計數排序法 (Counting Sort)
請由小到大重新排列整數序列 {a0, a1, ..., aN-1}。整數的值有上限。
計數排序法 | 輸入 計數排序法 | 輸出
演算法動畫
2021/05/15
希爾排序法 (Shell Sort)
希爾排序法 (Shell Sort)
請由小到大重新排列整數序列 {a0, a1, ..., aN-1}。
希爾排序法 | 輸入 希爾排序法 | 輸出
演算法動畫

排序演算法：比較表

演算法 時間複雜度 穩定性 原地排序 技巧 特色
氣泡排序法 氣泡排序法 二次函數 〇 〇

互換
× 不實用
選擇排序法 選擇排序法 二次函數 × 〇

互換
搜尋
× 不實用
插入排序法 插入排序法 二次函數 〇 〇

插入
〇當資料接近升冪排列時速度很快
Shaker Sort(篩動排序法) Shaker Sort
（篩動排序法)		 二次函數 〇 〇

互換
〇當資料接近升冪排列時速度很快
合併排序法 合併排序法 線性、對數 〇 ×

合併
後序
走訪
〇 穩定且快速
× 需要額外記憶體
快速排序法 快速排序法 二次函數 線性、對數 × 〇

分割
前序
走訪
× 速度會受基準值的選擇影響
〇 原地且快速
堆積排序法 堆積排序法 線性、對數 × 〇

堆積
× 執行速度有可能受系統影響
希爾排序法 希爾排序法 二次函數 線性、對數 × 〇

插入排序法
× 速度會受間隔的選擇影響
計數排序法 計數排序法 線性、對數 〇 ×

累積和
× 元素的值有上限
(元素值不宜太大)

第 21 章 基本資料結構 2


2020/05/17
雙向鏈結串列
雙向鏈結串列 (Doubly Linked List)
實作一個可以插入、搜尋及刪除元素的資料結構。
雙向鏈結串列 | 輸入
雙向鏈結串列 | 輸出
演算法動畫
2020/05/17
雜湊表 (Hash Table)
雜湊表 (Hash Table)
實作一個可以搜尋、新增及刪除資料，並提供字典功能的資料結構。
字典 | 輸入
字典 | 輸出
演算法動畫

第 22 章　廣度優先搜尋 (BFS)


2020/05/17
廣度優先搜尋 (BFS)
廣度優先搜尋 (BFS)
由適當的起點出發，系統性地走訪圖形中的所有節點。
廣度優先搜尋 | 輸入 廣度優先搜尋 | 輸出
演算法動畫
2020/05/17
利用 BFS 計算距離
利用 BFS 計算距離
找出從起點到各個節點的最短距離。此處的距離指的是走過的邊數。
利用 BFS 計算距離 | 輸入 利用 BFS 計算距離 | 輸出
演算法動畫
2020/05/17
卡恩演算法 (Kahn's Algorithm)
卡恩演算法 (Kahn's Algorithm)
從表示任務及其依賴關係的有向圖中，找出處理任務的
順序。
卡恩演算法 | 輸入 卡恩演算法 | 輸出
演算法動畫

第 23 章　深度優先搜尋 (DFS)


2020/05/17
深度優先搜尋 (DFS)
深度優先搜尋 (DFS)
由適當的起點出發，系統性地走訪圖形中的所有節點。
深度優先搜尋 | 輸入 深度優先搜尋 | 輸出
演算法動畫
2020/05/17
用 DFS 區分連通元件
用 DFS 區分連通元件
將圖形中的連通元件區分出來，並將同一連通元件內的節點塗上相同的顏色。
區分連通元件 | 輸入 區分連通元件 | 輸出
演算法動畫
2020/05/17
用 DFS 檢測迴路
用 DFS 檢測迴路
檢查有向圖中是否有迴路。
檢測迴 | 輸入 檢測迴 | 輸出
演算法動畫
2020/05/17
Tarjan 演算法
Tarjan 演算法
從表示任務及其依賴關係的有向圖，找出處理任務的順序。處理任務時，必須先完成該任務所依賴的所有任務。
拓撲排序 | 輸入 拓撲排序 | 輸出
演算法動畫

第 24 章　Union-Find Tree


2020/04/19
Union By Rank
Union By Rank
下圖為一座森林及森林內所有樹的根節點，請利用這些根節點將樹合併成新的森林。
合併樹 | 輸入 合併樹 | 輸出
演算法動畫
2020/04/19
路徑壓縮
路徑壓縮 (Path Compression)
請改變樹的形狀，以降低其高度。
路徑壓縮 | 輸入 路徑壓縮 | 輸出
演算法動畫
2020/04/19
Union-Find Tree
Union-Find Tree
請實作一個可以管理互不相交集合的資料結構。
Union-Find Tree | 輸入
Union_Find Tree | 輸出
演算法動畫

第 25 章　尋找最小生成樹的演算法


2020/05/17
普林演算法 (Prim's Algorithm)
普林演算法 (Prim's Algorithm)
請在加權無向圖中找出最小生成樹。
最小生成樹 | 輸入 最小生成樹 | 輸出
演算法動畫
2020/05/17
克魯斯克爾演算法
克魯斯克爾演算法 (Kruskal's Algorithm)
請從加權無向圖中找出最小生成樹。
最小生成樹 | 輸入 最小生成樹 | 輸出
演算法動畫

第 26 章　最短路徑演算法


2020/05/17
戴克斯特拉演算法 (Dijkstra's Algorithm)
戴克斯特拉演算法 (Dijkstra's Algorithm)
從加權圖形中的起點及終點找出最短路徑。
最短路徑問題 | 輸入 最短路徑問題 | 輸出
演算法動畫
2020/05/17
戴克斯特拉演算法 (優先佇列)
戴克斯特拉演算法 (優先佇列)
從加權圖形中的起點及終點找出最短路徑。
最短路徑問題 | 輸入 最短路徑問題 | 輸出
演算法動畫
2020/05/17
貝爾曼-福特演算法 (Bellman-Ford Algorithm)
貝爾曼-福特演算法 (Bellman-Ford Algorithm)
從加權圖形中的起點及終點找出最短距離。
最短路徑問題 (負權重) | 輸入 最短路徑問題 (負權重) | 輸出
演算法動畫
2020/05/17
弗洛伊德演算法 (Floyd-Warshall Algorithm)
弗洛伊德演算法 (Floyd-Warshall Algorithm)
利用加權有向圖的相鄰矩陣，建立一個可表示所有節點之間最短距離的矩陣。
所有節點間的最短路徑 | 輸入 所有節點間的最短路徑 | 輸出
演算法動畫

最短路徑演算法：比較表

演算法 時間複雜度 距離 技巧
廣度優先搜尋 廣度優先搜尋 線性 從單一起點到所有節點的最短路徑 (邊數) 佇列
戴克斯特拉演算法 (線性搜尋法) 戴克斯特拉演算法 (線性搜尋法) 二次函數 從單一起點到所有節點的最短路徑
※ 不得有負權重
戴克斯特拉演算法 戴克斯特拉演算法 線性、對數 從單一起點到所有節點的最短路徑
※ 不得有負權重 		優先佇列
貝爾曼 - 福特演算法 貝爾曼 - 福特演算法 三次函數 從單一起點到所有節點的最短路徑
可以有負權重
可檢測出負迴路
弗洛伊德演算法 弗洛伊德演算法 三次函數 各節點間的最短路徑
可以有負權重
可檢測出負迴路

第 27 章　計算幾何


2020/05/17
包裹法 (Gift Wrapping)
包裹法 (Gift Wrapping)
從一個點集合，求出凸包。
凸包 | 輸入 凸包 | 輸出
演算法動畫
2020/05/17
葛立恆掃描法 (Graham Scan)
葛立恆掃描法 (Graham Scan)
從一個點集合，求出凸包。
凸包 | 輸入 凸包 | 輸出
演算法動畫
2020/05/17
安德魯演算法 (Andrew's Algorithm)
安德魯演算法 (Andrew's Algorithm)
從一個點集合，求出凸包。
凸包 | 輸入 凸包 | 輸出
演算法動畫

第 28 章　線段樹


2020/05/17
線段樹：RMQ
線段樹：RMQ
更新區間最小值及取得指定區間的最小值。
Range Minimum Query | 輸入
Range Minimum Query | 輸出
演算法動畫
2020/05/17
線段樹：RSQ
線段樹：RSQ
實作在整數序列中的不同區間，求得指定區間的區間和。
Range Sum Query | 輸入
Range Sum Query | 輸出
演算法動畫

第 29 章　搜尋樹


2020/05/17
二元搜尋樹
二元搜尋樹 (Binary Search Tree)
實作一個可以搜尋、新增及刪除資料，並能管理與提供已排序元素的「字典」資料結構。
已排序字典 | 輸入 已排序字典 | 輸出
演算法動畫
2020/05/17
旋轉 (Rotate)
旋轉 (Rotate)
變換子樹。請確保變換前、後，透過中序走訪節點的順序不會改變。
旋轉 | 輸入 旋轉 | 輸出
演算法動畫
2020/05/17
樹堆 (Treap)
樹堆 (Treap)
請實作一個可以搜尋、新增及刪除資料，並能管理與提供已排序元素的「字典」資料結構。
已排序字典 | 輸入
已排序字典 | 輸出
演算法動畫

字典資料結構：比較表

資料結構 時間複雜度 記憶體效率 有無順序 應用
鏈結串列 鏈結串列 線性 〇 〇有順序 串列、字典
雜湊表 雜湊表 常數 × × 字典
二元搜尋樹 二元搜尋樹 線性 對數 〇 〇已排序 字典、集合、優先佇列、
最大值、最小值
樹堆 樹堆 樹堆 〇 〇已排序 字典、集合、優先佇列、
最大值、最小值


未收錄在書中的演算法



Last Update: