【C++ 筆記】基礎排序（氣泡、選擇、插入排序法）
===

[TOC]

本筆記僅供個人學習用途，內容斟酌參考。

1.Bubble Sort
---

原理：兩兩相鄰比較，大的往後推，重複進行多輪直到完成排序。

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        // 內層進行兩兩相鄰元素比較與交換
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

時間複雜度：
- 最佳情況： $O(n)$ （若資料已排序，可加入 flag 判斷是否有交換，避免多餘比較）
- 平均情況： $O(n^2)$ （每個元素都要比較一次）
- 最壞情況： $O(n^2)$ （完全反序，每輪皆需交換到最後）

空間複雜度： $O(1)$

算是穩定的排序法，也最常用。

2.Selection Sort
---

原理：每輪選出剩下的最小值，放到目前排序的位置。

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    // 每次選擇最小值放到前面
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i; // 假設目前最小值位置
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 將找到的最小值放到正確位置
        swap(arr[i], arr[minIndex]);
    }
}

時間複雜度：
- 最佳情況： $O(n^2)$ （無法透過資料特性提前結束，仍需全部比較）
- 平均情況： $O(n^2)$ （一共進行 $\frac{n(n-1)}{2}$ 次比較）
- 最壞情況： $O(n^2)$

空間複雜度： $O(1)$

該排序法不是那麼穩，因為交換過程中有可能會打亂相同元素的順序。

3.Insertion Sort
---

原理：從左至右逐一「插入」目前元素到左邊已排序好的序列中。

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i]; // 待插入的元素
        int j = i - 1;
        // 將比 key 大的元素往右移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 將 key 插入正確位置
        arr[j + 1] = key;
    }
}

時間複雜度：
- 最佳情況： $O(n)$ （若原序列已排序，不需移動，只需一次比較）
- 平均情況： $O(n^2)$ （中間情況需要約一半元素移動）
- 最壞情況： $O(n^2)$ （若為反序，則每插入一個元素都要移動全部前面的元素）

空間複雜度： $O(1)$

與 Bubble Sort 一樣穩，原因是不會改變相同值的順序。

總結
---

| 排序法 | 最佳時間複雜度 | 平均時間複雜度 | 最壞時間複雜度 | 空間複雜度 | 穩定性 |
| ---- | ----- | ----- | ----- | ---- | --- |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | 穩 |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | 不穩 |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | 穩 |

參考資料
---

[[C++] 氣泡排序法(Bubble sort). 簡單記錄一下自己的理解 | by Martin | Medium](https://medium.com/@oturngo/study-note-01-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95-bubble-sort-ee534b6f91eb)

[初學者學演算法｜排序法入門：選擇排序與插入排序法. 程式麻瓜的程式知識課（五） | by Cheng-Wei Hu | 胡程維 | Aiworks | Medium](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)

[Insertion sort (插入排序法). Insertion sort… | by Oliver Liao | Medium](https://medium.com/@ollieeryo/insertion-sort-%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-c215ae516a7ahttps://)