insertion_sort.cpp

// insertion_sort.cpp
// -----------------------------------------------------------------
// Insertion Sort（插入排序）
//
// 原理：像整理撲克牌——逐一取出元素，往左插入到已排序區的正確位置。
//
// 時間複雜度：最好 O(n)（已近乎排序）
//             平均 / 最壞 O(n^2)
// 空間複雜度：O(1)
// 穩定性：穩定
// 特點：對「幾乎已排序」或「小型」資料極快，
//       因此常作為 Quick/Merge/Tim/Intro Sort 的小區間收尾。
//
// Compile: g++ -std=c++17 -O2 -Wall -o insertion_sort insertion_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void insertionSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        // 比 key 大的元素整體右移一格
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

// 二分插入排序：用二分搜尋找插入點，比較次數降為 O(log n)（搬移仍 O(n)）
void binaryInsertionSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int pos = (int)(upper_bound(a.begin(), a.begin() + i, key) - a.begin());
        for (int j = i; j > pos; --j) a[j] = a[j - 1];
        a[pos] = key;
    }
}

static void printVec(const string& tag, const vector<int>& a) {
    cout << tag;
    for (int x : a) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<vector<int>> tests = {
        {12, 11, 13, 5, 6},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3, 4},          // 已排序 -> O(n)
        {4, 3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        insertionSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }

    vector<int> b = {9, 3, 7, 1, 8, 2, 5};
    printVec("binary insertion before: ", b);
    binaryInsertionSort(b);
    printVec("binary insertion after : ", b);
    cout << "sorted : " << boolalpha << is_sorted(b.begin(), b.end()) << "\n";
    return 0;
}