插入排序法 Insertion Sort

C++ 插入排序法參考程式

Insertion Sort 會把每個新元素插入左側已排序區段，直到整個陣列完成排序。

• 將目前元素存為 key，並向左比較。
• 比 key 大的元素會往右移動一格。
• 最後把 key 放入正確插入位置。

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = static_cast<int>(arr.size());

    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }

        arr[j + 1] = key;
    }
}

int main() {
    vector<int> data = {12, 11, 13, 5, 6};

    insertionSort(data);

    cout << "排序結果: ";
    for (int x : data) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}