tree_sort.cpp

// tree_sort.cpp
// -----------------------------------------------------------------
// Tree Sort（樹排序）
//
// 原理：把所有元素插入二元搜尋樹（BST），再做中序走訪取出，
//       中序走訪的結果天然有序。
//
// 時間複雜度：平均 O(n log n)；最壞 O(n^2)（BST 退化成鏈，
//             例如輸入已排序）。用平衡樹（AVL / 紅黑）可保證 O(n log n)。
// 空間複雜度：O(n)
// 穩定性：可做到穩定（相等元素插右子樹並保持插入順序）
//
// Compile: g++ -std=c++17 -O2 -Wall -o tree_sort tree_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>

using namespace std;

struct Node {
    int val;
    unique_ptr<Node> left, right;
    Node(int v) : val(v) {}
};

static void insert(unique_ptr<Node>& root, int v) {
    if (!root) { root = make_unique<Node>(v); return; }
    if (v < root->val) insert(root->left, v);
    else               insert(root->right, v);   // 相等走右 -> 穩定
}

static void inorder(const unique_ptr<Node>& root, vector<int>& out) {
    if (!root) return;
    inorder(root->left, out);
    out.push_back(root->val);
    inorder(root->right, out);
}

void treeSort(vector<int>& a) {
    unique_ptr<Node> root;
    for (int x : a) insert(root, x);
    vector<int> out;
    out.reserve(a.size());
    inorder(root, out);
    a = move(out);
}

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 = {
        {5, 4, 7, 2, 11},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3, 4},
        {4, 3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        treeSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}