基本演算法介紹-選擇.插入.快速排序法

實作1-排序演算法動畫操作

解說:

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

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

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

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

(1)找最小(大)值

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

(2)丟到左邊

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

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

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

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

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

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

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

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

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