shell_sort.cpp

// shell_sort.cpp
// -----------------------------------------------------------------
// Shell Sort（希爾排序）
//
// 原理：插入排序的改良版。以遞減的「間距」（gap）做分組插入排序，
//       讓元素能大步跳到接近最終位置，最後 gap=1 收尾（即插入排序，
//       但此時陣列已幾乎有序，插入極快）。
//
// 時間複雜度：取決於 gap 序列。
//   - 原始 Shell（n/2, n/4, ...）：最壞 O(n^2)
//   - Knuth（1, 4, 13, 40, ...）：約 O(n^{3/2})
//   - Sedgewick / Ciura 序列可更佳
// 空間複雜度：O(1)
// 穩定性：不穩定
//
// Compile: g++ -std=c++17 -O2 -Wall -o shell_sort shell_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Knuth gap 序列：1, 4, 13, 40, 121, ...（h = 3h + 1）
void shellSort(vector<int>& a) {
    int n = (int)a.size();
    int gap = 1;
    while (gap < n / 3) gap = gap * 3 + 1;

    for (; gap >= 1; gap /= 3) {
        // 對每個 gap 分組做插入排序
        for (int i = gap; i < n; ++i) {
            int key = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > key) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = 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 = {
        {23, 29, 15, 19, 31, 7, 9, 5, 2},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3, 4, 5},
        {9, 8, 7, 6, 5, 4, 3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        shellSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}