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

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

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;
    }
}