演算法學習筆記：氣泡排序（Bubble Sort）、插入排序（Insertion Sort）、選擇排序（Selection Sort）

（此為Wilsen Ren在Udemy開設之線上課程「資料結構與演算法 (JavaScript)」學習筆記，另有部分內容為自行補充，將持續隨著學習進度更新，若內容有誤，歡迎留言指正！）

氣泡排序（Bubble Sort）、插入排序（Insertion Sort）、選擇排序（Selection Sort）是三種概念較簡單的排序方式，空間複雜度皆僅要 O(1)，但平均時間複雜度皆達 O(n²)，除非要處理的資料量少，否則實務上少有應用。

氣泡排序（Bubble Sort）

由後而前依序將兩兩相鄰的值互相比較，直到所有的值都被排到正確的位置為止。

圖示

現假設有一陣列 [6,5,4,9,1]，要透過氣泡排序將陣列由小排到大的過程如下：

值得注意的是，當 i=(arr.length-2)=3 的迴圈跑完之後，只剩下 i=(arr.length-1)=4 的迴圈沒有跑，但經過前面幾輪迴圈，已能確定剩下的「9」必在最後一格，因此 i=(arr.length-1)=4 的迴圈可忽略不跑即排序完畢。

偽代碼&說明

若以「將陣列由小到大排序」為目標，則有指標「i」從第 0 項跑到倒數第二項，表示已經排序的範圍；另有指標「j」從最後一項跑到第 (i+1) 項，在此範圍內的相鄰值兩兩比較，左值小於右值則不變、左值大於右值則兩值互換。

只要兩相鄰值大小相等，兩者的相對位置就不會改變，因此屬於「穩定排序（stable sort）」。

程式碼範例（JavaScript）

function bubbleSort(arr){
    for(let i=0; i<=arr.length-2; i++){               //用指標i標示已經排序的範圍
        for(let j=arr.length-1; j>=(i+1); j--){       //指標j從尾往前走過所有未排序處
            if(arr[j-1]>arr[j]){                      //指標j對應的值與相鄰的值兩兩比較，若與目標順序不同則互相調換位置
                let temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

時間複雜度

氣泡排序使用雙層巢狀迴圈（nested loop），外層 i 從第 0 項走到 (arr.length-2) 項（次末項），在 i 之前的值代表已經排序好的資料；內層 j 從第 (arr.length-1) 項（最末項）開始走到第 (i+1) 項，用來將相鄰的值兩兩配對比較。現假設陣列中共有 (n+1) 筆資料（索引值從 0 到 n），時間複雜度分析如下：

1. 最差情況：O(n²)，若原陣列排序正好與目標順序完全相反，所有的值都被調換，最末項調換 n 次、次末項調換 (n-1) 次…第 1 項調換 1 次、第 0 項調換 0 次，全部共調換 [n+(n-1)+…+1+0] = [(n+0)*(n+1)]/2 = (n²+n)/2 次，O((n²+n)/2)=O(n²)。
2. 最佳情況：O(n)，若原陣列排序正好與目標順序完全相同，即 i 從第 0 項走到次末項，內層 j 的項目不需要執行，因此一共只有 (n-1) 個運算步驟，時間複雜度為 O(n)。
3. 平均情況：O(n²)，因使用巢狀迴圈，因此多數情況下會有 n*n 個運算步驟。

空間複雜度

O(1)，在排序過程中，資料只在原陣列當中比較、調換，需要的儲存空間固定，不需額外空間暫存資料。

插入排序（Insertion Sort）

從第二項起逐一取值當作「key」，並將其他所有的值依序跟「key」比較，其過程有如將「key」值從資料最末端依序往前掃描，直到找到正確位置後插入。

圖示

現假設有一陣列 [6,5,4,9,1]，要透過插入排序將陣列由小排到大的過程如下：

偽代碼&說明

若以「將陣列由小到大排序」為目標，則有指標「j」表示該輪循環中的「key」所在、指標「i」表示「key」值在該輪循環應在的位置。

找到「key」值應在位置之後，將「key」值放到第「i」項即完成該輪迴圈的排序。

插入排序是不斷找到「key」應在位置、並將「key」放入該位置的過程，並沒有將任何值對調，兩大小相等的值在排序後會按照原順序排列，因此屬於「穩定排序（stable sort）」。

程式碼範例（JavaScript）

function insertionSort(arr){
    for(let j=1; j<=arr.length-1; j++){     //從第1項開始設為key，逐一跟其他資料比較
        let key = arr[j];
        let i = j-1;                        //連同下方while迴圈，找到該輪循環key應在位置
        while(i>=0 && arr[i] > key){
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;                     //把key放到正確位置上
    }
    return arr;
}

時間複雜度

選擇排序使用雙層巢狀迴圈（nested loop），外層 j 從第 1 項走到 (arr.length-1) 項（最末項），在 j 之前的資料代表已經當過「key」；內層 i 從第 (j-1) 項開始走到第 (-1) 項，用來將資料中所有的值逐一跟「key」比較，以找出「key」的正確位置。現假設陣列中共有 (n+1) 筆資料（索引值從 0 到 n），時間複雜度分析如下：

1. 最差情況：O(n²)，若原陣列排序正好與目標順序完全相反，所有的值都被調換，第 0 項調換 1 次、第 1 項調換 2 次…次末項調換 (n-1) 次、最末項調換 n 次，全部共調換 [1+2…+(n-1)+n] = [(1+n)*n]/2 = (n+n²)/2次，O((n+n²)/2)=O(n²)。
2. 最佳情況：O(n)，若原陣列排序正好與目標順序完全相同，即 j 從第 1 項走到最末項，內層迴圈比較 i 與「key」不需執行，因此一共只有 (n-1) 個運算步驟，時間複雜度為 O(n)。
3. 平均情況：O(n²)，因使用巢狀迴圈，因此多數情況下會有 n*n 個運算步驟。

空間複雜度

O(1)，在排序過程中，資料只在原陣列當中比較、賦值，需要的儲存空間固定，不需額外空間暫存資料。

選擇排序（Selection Sort）

在所有資料值中，依序找出最符合目標條件者先排，直到每筆資料都被放到正確的位置為止。

圖示

現假設有一陣列 [6,5,4,9,1]，要透過選擇排序將陣列由小排到大的過程如下，綠底者代表當前最小值、黃底者代表正跟綠底最小值比較的值：

值得注意的是，當 i=(arr.length-2)=3 的迴圈跑完之後，只剩下 i=(arr.length-1)=4 的迴圈沒有跑，但經過前面幾輪迴圈，已能確定剩下的「9」必在最後一格，因此 i=(arr.length-1)=4 的迴圈可忽略不跑即排序完畢。

偽代碼&說明

若以「將陣列由小到大排序」為目標，則有指標「i」用來表示該輪循環中最小值應在位置、指標「j」從指標「i」處掃描到最後一筆資料，找出該輪循環的最小值。

找到最小值之後，將其放到 i 標示的應在位置上，在指標「i」以前的資料皆已經完成排序。

程式碼範例（JavaScript）

function selectionSort(arr){
    for(let i=0; i<=arr.length-2; i++){       //用指標i標示該輪循環最小值應在位置
        let min = i;
        for(let j=i; j<=arr.length-1; j++){   //用指標j找到該輪循環最小值，並設為第min項
            if(arr[j]<arr[min]){
                min = j;
            }
        }
        temp = arr[i];                        //將該輪循環最小值從第min項換到第i項；原在第i項者被換到原第min項，待後續比較
        arr[i] = arr[min];
        arr[min] = temp;
    }
    return arr;
}

對於兩大小相等的值而言，如果與之對調的值並非按照目標大小順序排列，則原本排序較前者可能被換到較後面的位置、原本排序較後者可能被換到較前面的位置，因此屬於「不穩定排序（unstable sort）」。

以下圖來說，目標順序是從小排到大，當綠色的 3 與其他值比較時，最小的值為 1、紅色的 3 與其他值比較時，最小的值為 2；但在排序前，2 的位置在 1 的前面，因此調換後，會變成綠 3 在後、紅 3 在前。

選擇排序為「不穩定排序」

時間複雜度

選擇排序使用雙層巢狀迴圈（nested loop），外層 i 從第 0 項走到 (arr.length-2) 項（次末項），用來代表當下最符合條件的值；內層 j 從第 i 項走到 (arr.length-1) 項（最末項），用來將資料中所有的值逐一跟「第 i 項」比較，以更新最符合條件的值。現假設陣列中共有 (n+1) 筆資料（索引值從 0 到 n），時間複雜度分析如下：

1. 最差情況：O(n²)，若原陣列排序正好與目標順序完全相反，所有的值都被調換，最末項調換 n 次、次末項調換 (n-1) 次…第 1 項調換 1 次、第 0 項調換 0 次，全部共調換 [n+(n-1)+…+1+0] = [(n+0)*(n+1)]/2 = (n²+n)/2 次，O((n²+n)/2)=O(n²)。
2. 最佳情況：O(n²)，若原陣列排序正好與目標順序完全相同，第 i 項與第 j 項依然要逐一比較，時間複雜度仍為 O(n²)。
3. 平均情況：O(n²)，因使用巢狀迴圈，不論最差或最佳情況都有 n*n 個運算步驟，平均時間複雜度仍為 O(n²)。

空間複雜度

O(1)，在排序過程中，資料只在原陣列當中比較、調換，需要的儲存空間固定，不需額外空間暫存資料。

三種排序法複雜度比較