前面讲了 STL 的 sort，但那毕竟是别人写好的。今天分享一个我自己写的排序函数——它会根据数组的实际情况，自动选择最合适的排序算法。我叫它 lxySort。

一、思路：没有最好的排序，只有最合适的

你可能听过各种排序：快排、归并、计数、基数、冒泡……每个都有自己的适用场景。那么问题来了：能不能写一个函数，自己判断"该用哪个"？

这就是 lxySort 干的事。它像个小管家，先看看这堆数据是什么情况，再决定派哪个"打手"上场。

刷题的时候，最烦的就是手写排序、查找、二分。其实 STL 早就给你备好了现成的，只要会用，能省一半时间。今天把最常用的三个记下来。

一、sort：排序神器

#include <algorithm>
#include <vector>

std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end());        // 从小到大
// 结果：1 2 5 8 9

// 从大到小
std::sort(v.begin(), v.end(), std::greater<int>());

// 自定义比较（按绝对值，或按结构体某个字段）
std::sort(v.begin(), v.end(), [](int a, int b) {
  return abs(a) < abs(b);
});

很多新手学完 new，就开始疯狂手动管理数组内存——new、delete[]、算大小、防越界……结果 bug 一抓一大把。其实 C++ 早就给你准备好了 std::vector，方便又安全。

一、vector 是什么？

一句话：一个能自动管理内存、想多长就多长的动态数组。

#include <vector>

int main() {
  std::vector<int> v;          // 空 vector
  v.push_back(10);             // 往尾部加一个
  v.push_back(20);
  v.push_back(30);             // 现在有 3 个元素
  return 0;
}

学 C++ 的时候，指针和数组永远是绕不开的两兄弟。它们看起来长得一样，用起来却处处是坑。这篇文章把我踩过的三个坑记下来，希望能帮你少走点弯路。

坑一：数组名到底是不是指针？

很多人背口诀：数组名就是首地址。这句话不全对，它只在"作为函数参数"时成立。

#include <iostream>

void func(int arr[]) {
  // 这里的 arr 已经退化成指针了
  std::cout << sizeof(arr) << std::endl; // 8，是一个指针的大小
}

int main() {
  int a[5] = {1, 2, 3, 4, 5};
  std::cout << sizeof(a) << std::endl; // 20，整个数组的大小
  func(a);
  return 0;
}

很多人学完指针，又看到 &，直接懵了——这东西到底是地址，还是引用？别急，今天把这两个"长相有点像"的家伙彻底分清楚。

一、先记住一句话

引用是变量的"别名"，不是变量本身。

int a = 10;
int &b = a;   // b 是 a 的别名
b = 20;       // 改 b 就是改 a
std::cout << a << std::endl; // 输出 20

1. 什么是算法复杂度

算法复杂度是衡量一个算法在执行过程中的资源消耗量的指标。通常分为 时间复杂度 和 空间复杂度 两种：

• 时间复杂度：表示算法执行所需的时间。
• 空间复杂度：表示算法执行过程中所需的存储空间。

2. 大O表示法

大O表示法用于描述算法复杂度的上界，主要关注的是算法在输入规模很大时，性能的增长情况。

• O(1)：常数时间复杂度，无论输入大小如何，算法总是执行相同数量的步骤。
• O(log n)：对数时间复杂度，随着输入规模的增加，算法执行的步骤按对数关系增加。
• O(n)：线性时间复杂度，算法执行的步骤与输入规模成正比。
• O(n log n)：线性对数时间复杂度，比线性时间复杂度稍差一些，常见于一些高级排序算法。
• O(n^2)：平方时间复杂度，步骤数量随着输入规模的平方增加，常见于一些简单的嵌套循环。
• O(2^n)：指数时间复杂度，步骤数量随着输入规模的指数增长。
• O(n!)：阶乘时间复杂度，极其低效的算法。

动态规划（dynamic programming）是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。

在本节中，我们从一个经典例题入手，先给出它的暴力回溯解法，观察其中包含的重叠子问题，再逐步导出更高效的动态规划解法。

"爬楼梯"

给定一个共有 $n$ 阶的楼梯，你每步可以上 $1$ 阶或者 $2$ 阶，请问有多少种方案可以爬到楼顶？

基本概念

分治算法是一种通过将较大规模的问题分解为较小规模的问题，并对这些较小问题求解，从而解决整个问题的算法。分治算法的核心思想是递归地将问题拆分并解决，这种方法在二分法中尤为明显。

分治算法（Divide and Conquer）是一种重要的算法设计范式。它通过将一个复杂的问题分解成若干个规模较小且相似的子问题，递归地解决这些子问题，再将子问题的解组合起来得到原问题的解。

分治算法的基本步骤

1. 分解（Divide）：

   • 将原问题分解成若干个规模较小的子问题。这些子问题通常是原问题的简化版本。

2. 解决（Conquer）：

   • 如果子问题规模足够小，直接解决；否则，递归地解决每个子问题。

3. 合并（Combine）：

   • 将子问题的解合并成原问题的解。

基本概念

贪心算法（Greedy Algorithm）在解决问题时，总是做出在当前看来是最优的选择。它只考虑局部最优解，并不从整体最优的角度考虑。因此，贪心算法的关键在于选择合适的贪心策略，该策略必须具备无后效性，即某个状态以后的过程不会影响之前的状态，只与当前状态相关。

注意：贪心算法并不适用于所有问题，选择的策略必须仔细分析是否满足无后效性，否则可能无法得到整体最优解。

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望能够得到问题的全局最优解的算法。贪心算法的核心思想是局部最优策略的累积能够带来全局最优。

图的基本概念

图（Graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。图 $G$ 可以抽象地表示为顶点集合 $V$ 和边集合 $E$ 的组合。通常情况下，图的数据结构会表示为 $G = \{ V, E \}$。