前面讲了 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);
});

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

搜索与回溯是计算机解题中常用的算法技术，特别适用于那些没有固定计算法则的问题。回溯是一种搜索算法中的控制策略，其核心思想是：尝试通过不断选择和探索不同的路径解决问题，如果当前路径行不通，就回退一步重新选择，直到找到解决方案或证明无解为止。
比如在迷宫问题中，探险者需要找到从入口到出口的路径。初始时，可以随意选择一个方向前进，一步步尝试前进。如果碰到死胡同，说明当前路径行不通，需要回退一步重新选择方向。这种不断前进、回退的过程，正是回溯算法的体现。

回溯算法的基本框架

回溯算法通常通过递归实现。下面提供两个常见的回溯算法框架

框架一：先遍历

递推算法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是在计算机数值计算中一个重要的算法。这种算法的特点是：一个问题的求解需要经过一系列的计算，在已知条件和所求问题之间存在某种相互联系的关系。在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，这种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般来说，可以将递推算法看成是一种特殊的迭代算法。

排序算法

在 C++ 中，排序算法是用来对数据进行排序的一种重要算法。排序算法根据其实现原理和时间复杂度的不同，可以分为多种不同类型。以下是一些常见的排序算法及其概念：

高精度计算

利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。

高精度计算中需要处理好以下几个问题：

1. 数据的接收方法和存储方法

数据的接收和存储：当输入的数很长时，可采用字符串方式输入，这样可输入位数很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。

void init(int a[]) {
    // 传入一个数组
    string s;
    cin >> s; // 读入字符串s
    a[0] = s.length(); // 用a[0]计算字符申s的位数
    for(int i = 1; i <= a[0]; i++) {
        a[i] = s[a[0] - i] - '0'; // 将数串s转换为数组a，并倒序存储
    }
}