教甄◆電腦科專業題庫下載題庫

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

1.找最小值
從「未排序好的數字」中找到最小值

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

O(n²)：選擇排序法 (Selection Sort)

時間複雜度為 O(n²) 的演算法，代表著執行步驟會跟著輸入 n 成次方比例的增加。最基礎的排序法之一：選擇排序法(Selection Sort) 是 O(n²) 複雜度的代表。

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

找最小值

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

丟到左邊

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

O(n²)：插入排序法 (Insertion Sort)

同樣擁有 O(n²) 時間複雜度，插入排序法 Insertion Sort 則是另外一個非常常見的排序法。簡單來說，插入排序法就是你玩撲克牌時用到的排序法。

讀一個數字

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

插入合適位置

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

合併排序法

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

拆分

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

把切好的兩個小陣列再各自切一半

重複步驟二直到每個小陣列都只剩一個元素

合併

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

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

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

快速排序法(Quick Sort)

快速排序法的概念

大致上來說，快速排序法就是先在序列中找出一個元素作為支點(pivot)，然後想辦法將比支點的元素移動到支點元素的左邊，比支點大的元素移動到支點元素的右邊，接著再用同樣的方法繼續對支點的左邊子陣列和右邊子陣列進行排