树排序
入门连接排序与数据结构，理解 BST 的有序性。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1struct Node { int value; Node *left, *right; };
2
3Node* insert(Node* root, int value) {
4 if (!root) return new Node{value, nullptr, nullptr};
5 if (value < root->value) root->left = insert(root->left, value);
6 else root->right = insert(root->right, value);
7 return root;
8}
9
10void inorder(Node* root, vector<int>& result) {
11 if (!root) return;
12 inorder(root->left, result);
13 result.push_back(root->value);
14 inorder(root->right, result);
15}
16
17void treeSort(int arr[], int n) {
18 Node* root = nullptr;
19 for (int i = 0; i < n; i++) root = insert(root, arr[i]);
20 vector<int> sorted;
21 inorder(root, sorted);
22 for (int i = 0; i < n; i++) arr[i] = sorted[i];
23}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n log n)
最坏 O(n²)
算法讲解
树排序将数组元素逐个插入二叉搜索树（BST）。
BST 的中序遍历会自然产生有序序列。
平均时间复杂度 O(n log n)，但最坏情况（退化为链表）为 O(n²)。
如果使用平衡 BST（如 AVL），可以保证 O(n log n)。