初级算法与数据结构入门指北

这是什么？算法？学一下。这是什么？算法？学一下。这是什么？算法？学一下。这是什么？算法？学一下。这是什么？算法？学一下。算法？学一下。这是什么？算法？学一下。

这是什么？数据结构？学一下。这是什么？数据结构？学一下。这是什么？数据结构？学一下。这是什么？数据结构？学一下。这是什么？数据结构？学一下。这是什么？数据结构？学一下。

本文不定期更新，同时也欢迎新生投稿，写下自己的疑问/笔记/理解/补充，如果相对文章进行补充或添加笔记，可以给出你的文章链接或文章内容（使用 markdown 和 LaTeX 格式可以更快过审），QQ 2545940612 或邮箱 chenza2024@shanghaitech.edu.cn。

---

注意事项：

1. 本文不包括任何编程语言的实例，只有伪代码，不要害怕读不懂伪代码，你只需要知道 $a\leftarrow b$ 意思是把 $b$ 赋值给变量 $a$，$a\leftrightarrow b$ 是交换 $a,b$ 的值，其他内容都和数学语言或程序语言类似。
2. 本文中，默认所有数组下标从 $1$ 开始，而不是 $0$.
3. 本文不采用传统的高斯符号 $[x]$ 来表示 $x$ 向下取整，而是使用 $\left\lfloor x\right\rfloor$ 表示 $x$ 向下取整，$\left\lceil x\right\rceil$ 表示 $x$ 向上取整。
4. 本文的 $\log$ 默认以 $2$ 为底数。当然可能以其他数为底数但是笔者没有注明，总之仅仅是表达一个对数级别的含义。

算法指北

前置内容

引

1-1-1-1

输入正整数 $n$，请你输出 $1+2+\ldots+n$ 的值。

这是一个非常经典的考察循环的题（如果你不想用循环写，请使用循环 .jpg），很容易写出下面的程序：

太漂亮的代码了！运行一下吧！让我们输入一个很小的 $n$，比如 $1145141919810$.

……等待程序运行出结果……

……等不了一点……

为啥？虽然计算机运行速度很快，但是也是有限的。循环 $1145141919810$ 次也会让计算机运行过久，导致一时间，甚至有生之年都无法得到结果。

这个时候突然有人有了个点子：

啪的一下就出结果了，很快啊！（注意 C++ 可能输出不正确的结果，原因是 $n(n+1)$ 太大导致溢出了。

这就是一种简单的算法，也就是优化暴力。

复杂度分析

分为时间复杂度和空间复杂度，这里重点介绍时间复杂度，空间复杂度类似。

时间复杂度，用来估计算法的时间，指算法的操作的数量。这么说太抽象了，举个例子，引子中用循环计算 $\sum i$ 的例子，每次循环都执行了一次加法，一共要循环 $n$ 次，所以时间复杂度是 $\mathcal O(n)$ 的，同时也是 $\Theta(n)$ 的。这里的 $\mathcal O$，$\Theta$，$n$ 的含义如下：

$n$ 表示复杂度与 $n$ 同级。随着 $n$ 增大，时间复杂度增大的级别和 $f(n)=n$ 这个函数增大的级别相同。这个可以用高数 / 数分学的等阶无穷理解。

• $\mathcal O$ 表示最坏，$\mathcal O(n)$ 也就是在最坏情况下，这个算法复杂度是 $n$ 同级的。

• $\Theta$ 表示恒定的，$\Theta(n)$ 也就是不管什么情况，算法复杂度都是 $n$ 同级的。

以上 $\mathcal O$ 和 $\Theta$ 是比较常用的两个符号。此外还有不怎么常用的符号：

• $\mathcal o$ 表示严格优，$\mathcal o(n^2)$ 表示即使在最坏情况下，算法复杂度也不会达到或超过 $n^2$ 级别。
• $\Omega$ 表示最好，$\Omega(n)$ 表示在最理想的情况下，算法复杂度是 $n$ 同级的。
• $\omega$ 表示严格劣，$\omega(n)$ 表示即使是最好的情况，算法复杂度也会严格劣于 $n$ 级别。

空间复杂度类似，表示程序需要使用的内存，例如 $\mathcal O(n)$ 空间复杂度表示最坏情况下需要使用与 $n$ 同级的数量的变量（即这么多变量占用的空间）。

观察下面的两个程序（Algorithm3 和 Algorithm4），分析它们的时间复杂度。

题解

• 第一个程序，时间复杂度为 $\Theta (nm)$，也可以写成 $\mathcal O(nm)$.
• 第二个程序，看起来有两重循环，最坏情况下 $l,r$ 两个变量也确实都能取遍 $[1,n]$，但实际上，$l,r$ 取遍 $[1,n]$ 是并列的，不是嵌套的（即 $l=1$ 时 $r$ 取遍一次 $[1,n]$，$l=2$ 时 $r$ 又取遍一次 $[1,n]$……以此类推）。还有一种思路，就是对于每一个 $a_i$，要么被略过，要么被加进答案，这两种情况都会出现恰好一种的恰好一次。所以复杂度是 $\Theta(n)$，也可以写成 $\mathcal O(n)$ 的。

另外，第二个程序本质上相当于使用 $r$ 的移动跳过了值为 $0$ 的元素参与求和计算，所以结果是正确的。

而对于引子里直接使用公式计算答案的情况，我们一般记作他的时间复杂度是 $\mathcal O(1)$ 的，即常数级的。

后文中，不会刻意拘泥于 $\mathcal O$，$\Theta$ 等的使用，笔者习惯全部写成 $\mathcal O$。

此外，除了复杂度，我们可能还会说一个程序“常数很小”或“常数很大”，毕竟 $\mathcal O$ 这种东西衡量的也就是增长的级别，都是 $\mathcal O(n\log^2 n)$ 的东西，有些东西可能一秒能跑 $2\times 10^5$ 的数据，有的可能只能跑 $5\times 10^4$ 规模（连 $n\log n$ 都不如）。

在算法竞赛中，通常直接把 $n,m$ 等带入复杂度表达式，如果得出的结果为 $10^7$ 数量级或者刚好 $10^8$（大约在 $4\times 10^8$ 以内都是可以接受的），说明这个复杂度的算法使用 C++ 实现是可以 1s 内通过的。但是极端情况下请不要忽视常数带来的影响（不过等到各位需要考虑常数问题的时候，大概率已经走出入门了！）。通常情况下，数据范围意味着的时间复杂度为：

$n\leq$	对应的可能复杂度	$n\leq$	对应的可能复杂度
$10$	$n!$ 或 $n!\cdot n$	$10^5$	$n\log n$ 或 $n\log^2 n$
$14$	$3^n$ 或 $3^n\cdot n$	$5\times10^5$	$n\log n$
$20$	$2^n$ 或 $2^n\cdot n$	$10^6$	$n\log n$ 或 $n$
$25$	$2^n$	$10^7$	$n$
$40$	$2^{\frac{n}{2}}$	$10^9$	$1$, $\log n$ 或 $\sqrt n$
$50\sim100$	$n^4$	$10^{10}$	$n^{\frac{2}{3}}$（杜教筛）
$200\sim500$	$n^3$	$10^{11}$	$\frac{n^{\frac{3}{4}}}{\log n}$（min25 筛）
$1000\sim 5000$	$n^2$	$10^{12}$	$1$, $\log n$ 或 $\sqrt n$
$5\times 10^4$	$n\sqrt n$	更大	$1$, $\log n$ 等，视情况判断

tips: $n\leq 10^{10}$ 的数论问题通常意味着杜教筛，$n\leq 10^{11}$ 的数论问题通常意味着 min25 筛（分别是求一类数论函数前缀和和一类积性函数前缀和的算法，如 $\sum_{i=1}^n \varphi(i)$，其中 $\varphi$ 为欧拉函数）。问题和算法都已经涉及到比较难的解析数论知识，本文不会讨论，也不建议读者现在学习。

优化暴力的思想

通常所说的“暴力”，类似于数学考试考组合数学的时候，使用穷举法硬解的算法。一般是指的不需要脑子的暴力，在大部分情况下都思想简单，代码实现难度不大。暴力思路因为几乎贴着题意，枚举所有的东西然后求解，所以大部分情况下都不难想到，而正解有可能就是对暴力做法的优化：或许这里的枚举是不必要的？或许这里的递归可以优化？或许在满足题目给出的特殊性质之后，有些在一般情况下需要暴力计算的东西有特殊方法可以算出来……

在本文中，我们默认讨论的是复杂度级别上的优化，是直接改变时间复杂度，而不是减小常数（例如 $n$ 次循环变成 $\frac{n}{2}$ 次循环，显然这还是 $\mathcal O(n)$ 的）。

1-1-3-1

给定大小为 $n$ 的数列 $\{a_n\}$，进行 $m$ 次询问，每次询问给出 $l,r$，你需要对于每次询问求 $a_l+a_{l+1}+\ldots+a_r$ 的值。

对手每一次询问，我们都可以写一个从 $l$ 到 $r$ 的循环去求 $a_l+a_{l+1}+\ldots+a_r$ 的值。显然这样的复杂度是 $\mathcal O(nm)$ 的，最坏情况是每次询问都问 $l=1,r=n$。

预先算好 $S=a_1+a_2+\ldots+a_n$，如果询问 $l=1,r=n$ 直接输出 $S$？治标不治本，如果每次都问 $l=2,r=n$，你的程序就还是会枚举，每次询问循环了 $n-1$ 次，复杂度还是 $\mathcal O(nm)$ 不变。

但是这个做法给了一个提醒：我们好像可以预先算好一些东西，来方便化或简化后续中心处理部分。这个“预先算好”这一步，叫做预处理。

由于预处理和中心处理部分是两个部分，先进行前者后进行后者，所以复杂度计算时，等同于两者分别的复杂度相加而不是相乘。

于是答案呼之欲出了：我们预先算好另外一个数列 $\{s_n\}$ 表示 $\{a_n\}$ 的前 $n$ 项和数列（也叫前缀和数列），即 $s_i = \sum_{j=1}^i a_j$，关于 $\{s_n\}$ 的计算，不难有递推式 $s_{n+1} = s_n + a_{n+1}$。于是这方面复杂度为 $\mathcal O(n)$。

既然已经知道了前 $n$ 项和，那么对于每次询问求 $a_l+a_{l+1}+\ldots a_r$，等价于求 $s_r - s_{l-1}$（特别地，记 $s_0=0$），单次询问 $\mathcal O(1)$ 计算，故询问部分是 $\mathcal O(m)$，因此实现了复杂度为 $\mathcal O(n+m)$ 的算法。

显然，这个题要先输入 $n$ 个数，然后输入 $m$ 组询问，输入复杂度就已经 $\mathcal O(n+m)$ 了，算法复杂度再低也没必要了。处理部分的伪代码如下：

给定大小为 $n$ 的数列 $\{a_n\}$，求它的和最大的子串（可以为空，此时子串和为 $0$）。

题解

依然可以按照例题的方案，求出前缀和 $\{s_n\}$。那么一个子串 $\{a_l,a_{l+1},\ldots,a_r\}$ 的和为 $s_r-s_{l-1}$，而我们需要找到它的最大值。

直接枚举所有的 $l,r$，复杂度是 $\mathcal O(n^2)$ 的，但是注意到对于一个固定的 $l$，使 $s_r-s_{l-1}$ 最大的 $r$ 一定满足 $s_r$ 尽量大。于是我们可以记录 $mx_i$ 表示已知 $l=i$ 的前提下，$s_r$ 的最大值，那么答案变为求 $\max\{mx_i-s_{i-1}\}$，这个可以通过枚举 $i$ 实现 $\mathcal O(n)$ 复杂度。

对于 $mx_i$，因为有 $r\geqslant l$ 这一硬限制，所以有 $mx_n = s_n$，那么从 $n$ 到 $1$ 循环，反向递推 $\{mx_n\}$，有 $mx_{i-1} = \max\{ mx_i,s_{i-1} \}$，是 $\mathcal O(n)$ 复杂度的。

预处理 $\{s_n\}$，再预处理 $\{mx_n\}$，根据 $\{mx_n\}$ 算答案，这三步分别复杂度是 $\mathcal O(n)$，因此总复杂度是 $\mathcal O(n)$。

本题具体实现时，有一个坑点，子串可以为空：如果所有数都是负数，那么选空子串就是最优解，解决方案之一是令答案的初始值为 $0$。伪代码如下：

当然，如果不喜欢从后往前推，可以换一种形式：固定 $r$，记录 $mn_i$ 表示已知 $r=i$ 的前提下，$s_l$ 的最小值。这和上面的方法类似。

1-1-3-2

给定大小为 $n$ 的数列 $\{a_n\}$，进行 $m$ 次修改操作，每次操作给出 $l,r,x$，将 $a_l,a_{l+1},\ldots,a_r$ 这些值加上 $x$。你需要求序列在经过所有修改操作后的结果。

暴力做法就是对于每一次操作，枚举并把 $a_l,a_{l+1},\ldots,a_r$ 分别加上 $x$，单次操作最坏复杂度是 $\mathcal O(n)$，因此时间复杂度是 $\mathcal O(nm)$ 的。

因为操作数已经固定是 $m$ 次了，难以优化这个 $m$，因此考虑能不能优化单次操作的最坏复杂度。需要注意的是：我们并不关心这个数组实时的状态是什么，我们只需要找出所有的操作完成之后的数组长什么样。

一个显然成立的式子是，若 $a-b=c$，则 $(a+x)-(b+x)=c$. 因此，我们类比前面的“前缀和”，尝试构造数列 $\{d_n\}$，使得 $d_1=1,d_{n+1}=a_{n+1}-a_n$（或者，另一种写法，直接记 $a_0=0$，就可以写成 $d_n = a_n-a_{n-1}$ 而不考虑 $n=1$ 的特殊情况），这样的数列 $\{d_n\}$ 被称为 $\{a_n\}$ 的差分数列。

差分有什么性质呢，注意到 $a_l,a_{l+1},\ldots,a_r$ 都加上 $x$ 变成 $a_l+x,a_{l+1}+x,\ldots,a_r+x$，这一段区间内部：$a_{l+1}-a_l,a_{l+2}-a_{l+1},\ldots,a_r-a_{r-1}$ 这些值，也就是 $d_{l+1},d_{l+2},\ldots,d_{r}$ 都不会改变。对于严格在区间外面的 $d_1,d_2,\ldots,d_{l-1}$ 以及 $d_{r+2},d_{r+3},\ldots,d_n$，显然也没有改变。那么，只有 $d_l = a_l-a_{l-1}$ 和 $d_{r+1} = a_{r+1}-a_r$ 这两个差分值发生了改变。具体的改变为：$d_l$ 变成 $d_l+x$，而 $d_{r+1}$ 变成 $d_{r+1}-x$.

那么，单次操作，虽然有线性级别（具体数目为 $r-l+1$ 个）的 $a_i$ 的值发生了改变，但是只有两个差分值发生了改变。也就是说，我们不再动态地去维护 $\{a_n\}$，而是求出一开始的数组对应的差分数组 $\{d_n\}$，然后每次操作都只会修改 $\{d_n\}$ 的两个值。所有 $m$ 此操作结束后，可以通过操作完毕后的 $\{d_n\}$ 算出操作完毕后的 $\{a_n\}$.

从 $\{a_n\}$ 得到 $\{d_n\}$ 和从 $\{d_n\}$ 得到 $\{a_n\}$ 的复杂度都是 $\mathcal O(n)$，单次操作的复杂度 $\mathcal O(1)$. 整个流程的复杂度是 $\mathcal O(n+m)$ 的。伪代码如下：

1-1-3-3

观察下面的程序，这是一个求斐波那契数列第 $n$ 项的程序（$f_1=f_2=1,f_n=f_{n-1}+f_{n-2}\,(n\geqslant 3)$），分析它的时间复杂度，然后将这份代码做简单修改以优化它。

如果你选择瞟一眼观察一下递推式，很可能认为它的时间复杂度是 $\mathcal O(n)$，也就是线性的，因为就是一个递推。但是如果你看一眼这个程序，可能会发现一些端倪。

如果没什么想法，不妨试一试手动模拟一下程序怎么运行求 $f(5)$ 的：求 $f(5)$ 会先递归求 $f(4)_1$ 和 $f(3)_1$。求 $f(4)_1$ 会先递归求 $f(3)_2$ 和 $f(2)_1$。求 $f(3)_2$ 会先递归求 $f(2)_2$ 个 $f(1)_1$，这两个是递归边界。然后回到上一个求 $f(2)_1$，这个也是边界。然后回到上一个求 $f(3)_1$ 的位置，求 $f(2)_3$ 和 $f(1)_2$. 这两个是递归边界。于是计算出来 $f(5)$ 的值。如果文字描述不太直观的话，下面的图可以辅助你理解：

发现了吗，每个 $f(n)\,(n\geqslant 3)$ 都会递归地求 $f(n-1)$ 和 $f(n-2)$. 复杂度是 $\mathcal O(2^n)$，而不是 $\mathcal O(n)$.

问题出在哪里？看这个图可以发现，当我们求 $f(5)$ 的时候，会递归地求 $f(4)$ 和 $f(3)$，而我们求 $f(4)$ 的时候，会递归地求 $f(3)$ 和 $f(2)$——$f(3)$ 被计算了两边。也就是说，非常多的项在被重复地计算，导致了复杂度的退化。

那么如何保证每个函数只被计算一次？我们记录一下被计算过的值就可以了：

我们把 $mem$（也就是 memory，记忆数组）的值赋为不可能出现的数字（比如 $-1$），然后，如果当前的 $f(n)$ 没算过就算，然后记忆一下结果；如果算过了，就说明记忆数组里 $mem_n$ 不为初始值，则再求这个 $f(n)$ 的时候，会进入第六行的 if 从而直接返回，避免递归下去进行不必要的计算。复杂度就可以变成和正常递推一样的 $\mathcal O(n)$ 了。

在这个题目中，进行记忆化能得到正确答案是毋庸置疑的，但是并不是什么时候都可以无脑记忆化。例如：对于一个二元函数 $f(n,m)$，你不能通过只用 $mem_n$ 来通过记忆化 $n$ 优化复杂度，因为 $n$ 相同而 $m$ 不同的情况，函数值不同，所以应该用 $mem_{n,m}$ 来记忆化。

更换新的思路

有时候，单纯的从暴力做法进行优化，也无法得到最优复杂度。开辟新的思路也是非常重要的。

1-1-4-1

给定大小为 $n$ 的数列 $\{a_n\}$，你需要求其所有子串的数和的和，子串的定义是原序列的一个连续段。单独的一个元素也可以认为是一个子串。

我们可以先枚举 $l,r$，将子串 $\{a_l,a_{l+1},\ldots,a_r\}$ 提出来，求和，把这个和累加到答案变量上。如果是先枚举 $l,r$，再把子串扫一遍求和，时间复杂度是 $\mathcal O(n^3)$。

注意到枚举 $l$ 之后，枚举 $r$ 的时候，当 $r$ 变成 $r+1$ 时，当前子串的和与之前子串的和相比仅仅是多加了一个 $a_r$，因此可以一遍枚举 $r$ 一边实时递推当前的子串的和，时间复杂度优化到 $\mathcal O(n^2)$。当然，也可以预处理前缀和，然后枚举 $l,r$ 之后 $\mathcal O(1)$ 计算当前子串的和，时间复杂度还是 $\mathcal O(n^2)$。

难道这个题只能 $\mathcal O(n^2)$ 做？答案是否定的，我们需要换一个思路来做这个题。我们从“考虑计算每一个子串对答案产生的贡献”（也就是每个子串的数字和是多少）这种思想切换成“考虑每个数字对答案产生的贡献”。假设 $a_i$ 一共出现在 $cnt_i$ 个子串里，那么 $a_i$ 这个数就会参与 $cnt_i$ 个子串里的求和，那么 $a_i$ 就会被加 $cnt_i$ 次，那么 $a_i$ 对答案的贡献就是 $a_i\times cnt_i$. 换句话说，这个题的答案应该是：

$ans = \sum_{i=1}^n a_icnt_i$

现在考虑如何计算 $a_i$ 这个元素出现在了多少个子串里。注意到假设一个子串的左端点为 $l$，右端点为 $r$，则只要 $i\in[l,r]$，$a_i$ 就会被包括在子串 $\{a_l,a_{l+1},\ldots,a_r\}$ 中。那么对于 $l$，它可以取 $[1,i]$ 的任意整数，$r$ 可以取 $[i,n]$ 的任意整数，每个这样的取法都是符合条件的。换句话说，$cnt_i = i(n-i+1)$.

求 $cnt_i$ 复杂度是 $\mathcal O(n)$，求 $ans$ 复杂度也是 $\mathcal O(n)$，故整体复杂度为 $\mathcal O(n)$.

类似的，一个问题如果无法从优化暴力的角度解决的时候，多想想是不是有其他做法。事实上，大部分的题目，正解都和暴力大相径庭。

将一个序列 $\{a_n\}$ 恰好划分为任意个连续段 $[l_1,r_1],\ldots,[l_m,r_m]\,(l_1=1,r_m=n)$. 定义第 $i$ 段的分数为：

$i\cdot\sum_{j=l_i}^{r_i} a_j$

你需要求所有的划分方案中，每一段的分数的和最大的方案对应的分数和。

题解

暴力的话，就是枚举所有的划分方案，然后对于这个划分方案，计算分数和。将长度为 $n$ 的序列划分为任意个连续段，总的划分方案有 $2^n-1$ 种（至于如何计算这个值：考虑第一个数当第一段，随后对于每个数字，要么这个数字作为划分点开启了新的一段；要么这个数字不是划分点和上一个数字在同一段）。计算分数和又是 $\mathcal O(n)$ 的，于是暴力的总复杂度为 $\mathcal O(n2^n)$.

因为划分方案就是有指数级别的数量个，所以只要是对于每个划分方案都进行计算，必然摆脱不了这个 $2^n$ 卡在复杂度里面，实在是太大了，所以考虑不枚举这个。也就是直接算。

一栋层数为无限（地面上楼高无穷，地下室楼深负无穷）的大楼。有一个电梯，最多只能装一个人。有 $n$ 个人，每个人分别希望从 $l_i$ 楼坐电梯到 $r_i$ 楼（$l_i<r_i$）。电梯上升需要消耗 $1$ 单位地电，下降不需要消耗电（无论电梯里是否有人）。电梯初始的时候可以停在任意某个楼层，送这 $n$ 个的顺序也能任意定，求最少需要消耗的电。

题解

假设我们已经确定好了送 $n$ 个人的顺序并排好了序，那么可以不妨钦定电梯初始的时候就在第一个人所在的楼层 $l_1$，因为如果电梯初始的时候不在这个楼层，就一定需要先移动到这个楼层。于是我们就可以不再考虑电梯的初始楼层，避免楼层数是无穷枚举不便的问题。

那么暴力做法就是枚举送 $n$ 个人的顺序（如何枚举顺序将在本文的后面部分提到），然后计算电梯消耗的电力（这一部分复杂度至少为线性），因为顺序有 $n!$ ，种所以复杂度是 $\mathcal O(n!\cdot n)$ 的。由于我们很难做到少枚举很多顺序，枚举顺序产生的这个 $n!$ 的复杂度也十分巨大，想要做出这个题，不得不放弃枚举顺序的思路。

总消耗的电力应当等于把每个人送到它要去的层消耗的电力，加上，送完人后移动到下一个人所在的层消耗的电力。需要注意，无论接人的顺序是什么，把每个人从 $l_i$ 层送到 $r_i$ 层所消耗的电力（也就是 $r_i-l_i$）是必需的。而假设电梯移动到了一个很高的层 $R$，现在移动到下一个人所在的层 $L$，只要 $R\geqslant L$ 就可以使得在这两个人之间移动的电力零消耗。

因此我们把每个人按照 $r_i$ 从大到小排序。因为 $l_i<r_i$，所以因为送前一个人电梯移动到了更大的 $r_i$，对于后一个人有 $l_{i+1}<r_{i+1}\leqslant r_i$，所以电梯送完前一个人之后一定是下降楼层去后一个人的位置，这样的话送完前一个人后移动到后一个人所消耗的电力就一定是 $0$.

这么做的话只有每个人从其所在楼层到目的楼层这个过程消耗了电力，电梯移动到下一个人所在楼层这个部分不消耗电力，故答案为 $\sum (r_i-l_i)$. 因为题目不要求你输出接人的顺序，你可以不排序，直接算 $\sum (r_i-l_i)$ 并输出，时间复杂度为 $\mathcal O(n)$.

排序

接下来我们将会正式进入算法部分。后续的习题将会如同正常问题般给出标准的数据范围。以辅助你的思考。此外，后续的例题和习题可能会给出 Si100minus 上

1-2-1-1

给定大小为 $n$ 的数列 $\{a_n\}$，你需要对 $\{a_n\}$ 按升序排序。

题目连接：[Template] Sort

这个题目看起来简单，但是如何切入呢？

选择排序

从“升序排序”这一点出发，升序就是最小的数放前面、第二小的数放第二个……最大的数字放最后面。

于是我们可以考虑模拟上述的过程：找到最小的数字，然后把它放在第一个位置，然后找第二小的数，把它放在第二个位置……

这样的排序方法叫做选择排序。选择排序的思路很好理解，如何实现？

注意到，当我们找到了最小的数字并放在第一个位置之后，剩下的数字里面最小的数字就是整个数列第二小的数字。

于是可以写出如下的程序：

注意，因为方便，这里记录的 $min$，并不是当前最小的数的数值，而是最小的数所在的下标。我们找到最小的数的位置之后，就可以通过交换 $a_i,a_{min}$（第八行），把最小的数放到第 $i$ 个位置。而被换走的原来的 $a_i$，我们不用管，因为它在后续的操作中一定也会被换到正确的位置上。

不难发现，这个做法的时间复杂度为 $\mathcal O(n^2)$.

插入排序

插入排序的切入点在于：假设我已经有了一个有序的数列，如何在里面增加一个新的数？

不难发现，我们可以逐个比对当前要增加的数字和其他的数字的大小，直到找到这个数字应该放进去的位置，然后把这个数插入进去。

但是这么做的前提是我有一个有序的数列，有序的数列怎么来呢？

我们可以认为最开始我们只有一个数组成的序列（或者压根没有数，只有一个空序列），然后按照这种方法把 $\{a_n\}$ 里的数一个一个插入进去就可以了。

复杂度是 $\mathcal O(n^2)$ 的。虽然每次插入一个数时，找插入的数应该插入到的位置可以使用二分查找，但是插入这个位置涉及到这个位置后面的数的下标全部 $+1$，所以实际复杂度还是 $\mathcal O(n^2)$ 的。那还不如直接线性地一个个查，复杂度也没变，二分反而容易写错。

这段程序的意思是，我们假定 $1$ 到 $i-1$ 这一段已经排好序了，现在我们即将插入数字 $a_i$. 与上面的图例一样，我们选择从大到小地去寻找 $key=a_i$ 需要插入的位置，直到我们找到了合适的位置（也就是第一个一个 $j$ 使得 $a_j\leqslant key$）。

在寻找的过程中，把这些数列整体往右边挪动，这样就省略了先找到位置之后，把这个位置后面的数往后面挪来空出位置放这个数的过程（本质上就是把找数和挪位置两步合在一起了）。

冒泡排序

冒泡排序的切入在于：如果每次只考虑相邻的两个数字，如果大的数字在前面小的数字在后面，我们就交换这两个数。

在这种情况下，我们考虑“跟踪”一下整个序列最大的数所在的位置：不难发现经过　最多 $n-1$ 次交换（这种情况下，最大的数字在原数列的第一项），这个最大的数就会被换到整个数列的最右边。

那么我们就索性从左到右依次检查相邻的两个数，不管最大的数在哪里，这一轮下来它就一定归位了。以此类推，我们再从左到右检查一次，第二大的数一定就归位了……我们执行 $n$ 轮这样的检查，所有的数就可以归位。

因为要检查 $n$ 次，每次检查都是 $\mathcal O(n)$ 级别的，复杂度是 $\mathcal O(n^2)$ 的。冒泡排序的代码实现也很简单，是最受欢迎的 $n^2$ 级排序算法。

快速排序

快速排序，字面意思，它快。但是它不完全快。

快速排序使用了一种分治的思想：所谓分治，就是分而治之，把原来的问题分解成两个相同的部分，分别求解之后合并两个部分的答案。例如，把计算 $f(1)+\ldots+f(n)$ 分解成计算 $f(1)+\ldots+f(\left\lfloor\frac{n}{2}\right\rfloor)$ 和计算 $f(\left\lfloor\frac{n}{2}\right\rfloor)+\ldots+f(n)$, 然后把两个指加起来。分治通常都用递归来解决。

那么快速排序的核心思想是什么呢？

假设我把原序列 $\{a_n\}$ 划分成了两个序列 $\{p_{m_1}\}$ 和 $\{q_{m_2}\}$，其中 $m_1+m_2=n$. 满足 $\forall x\in\{p_{m_1}\},\forall y\in\{q_{m_2}\},x\leqslant y$. 也就是说，前一个序列内所有数都不大于后一个序列的任意数。但是不保证 $\{p_{m_1}\}$ 和 $\{q_{m_2}\}$ 有序。

那么我对这两个数列分别排序得到 $\{p_{m_1}'\}$ 和 $\{q_{m_2}'\}$，那么总的排序后的数列就应该是 $p'+q'$.

于是我们就有了一个基于分治思想的排序算法：

1. 将当前序列按某种方式分成两个序列，使得一个序列所有的数都不大于另一个序列的任意数。
2. 将两个序列分别排序。这一步需要用递归实现（也就是，在排这两个序列的时候，需要继续按某种方式划分，然后分别排序划分得到的子序列……）。
3. 将两个序列合并，也就是直接拼接起来。如果你实现第一部的时候，已经把两个数列中一个放左边，另一个放右边了，这一步就不需要了（参见下面的动图）。

第二步是递归实现，第三步是直接把两个序列拼起来。关于第一步，我们如何把这个序列按某种方式划分成两个序列，使得一个序列所有数不大于另一个序列的任意数？

一种好的方法是进行浑水摸鱼：我们可以线性地求出当前序列的最大值和最小值，然后在这两个值之间随机选择一个阈值 $k$，将所有值 $<k$ 的放在一个序列里，值 $\geqslant k$ 的放在另一个序列里。

在下面的图片中，我们默认 $k$ 去当前排序的序列的第一项（标黄），把 $<k$ 的值分成一个序列（标绿），$\geqslant k$ 的值为另一个序列（标紫）。

这样做，最好情况下，每次选的 $k$ 都能选到中位数，也就是把数组分成大小几乎相等的两半，那么可以算出复杂度是 $\mathcal O(n\log n)$ 的。最坏情况下，每次随机到的 $k$ 都是数列的极值或十分接近极值的数，每次划分数列只能划分成一个和原数列几乎等长的数列和一个只含有几个数的数列，复杂度会变成 $\mathcal O(n^2)$. 也就是说，这个算法的复杂度是 $\Omega(n\log n),\mathcal O(n^2)$ 的。

当然，因为每次都随机到接近极值的数概率很小，所以你还是可以认为这个算法的效率很高的。

因为伪代码很难写，所以下面给出的程序不是把阈值 $k$ 取为随机数的算法，而是和例图一样直接取第一个数的算法。需要注意的是，在算法竞赛或有关的做题网站、比赛网站中草率地使用这种做法，复杂度很容易被卡成 $n^2$ 从而寄掉。

归并排序

归并排序是应用非常广泛的排序，在后续的学习中，你会遇到很多使用归并排序或其衍生思想能解决的问题。因此学会归并排序是很重要的，比楼上那个垃圾还会被卡的快排有用多了。

不过归并排序的常数略大，实现的时候代码尽量漂亮一点，写太丑了容易强化归并排序的常数问题。

归并排序的切入点在于：假设我已经有了两个有序（且同向，例如都是从小到大）的数列，能否把这两个有序的数列合并成一个有序的数列？

不难发现，我们每次比较两个有序数列中的最小值，然后把最小的那个数拎出来加入到当前序列里。如此反复直到两个序列被取完，我们就实现了把两个有序数列合并成一个有序数列，且时间复杂度为线性。

于是，我们可以类比快速排序，基于分治思想，给出如下的算法：

1. 将当前序列分成两个序列。
2. 将两个序列分别排序（递归）。
3. 将两个排好序的序列合并。

这里，将序列分成两个序列就可以任意划分，不需要满足特定的性质。不难想到每次到把当前的序列平分成两半，可以获得最优复杂度。总的复杂度是 $\mathcal O(n\log n)$ 的。

归并排序的程序较长，长的部分主要是实现将两个有序数列合并的部分：

给定一个大小为 $n$ 的数列 $\{a_n\}$. 你需要求出数列的逆序数，也就是逆序对数。$n\leq 10^5$.

$\{a_n\}$ 的逆序对的定义为一个有序数对 $(i,j)$ 满足 $i<j,a_i>a_j$.

题目链接：Inverse Pair

提示

假设数列长成 $p+q$ 的形式，其中 $p,q$ 分别都是从小到大排好序的，如何计算这个数列的逆序数（尝试用 $\mathcal O(n)$ 的做法解决）？

这个假设是不是和归并排序很相似？

题解

假设数列被分成了两半，左半部分数列 $p$ 是排好序的，右半部分 $q$ 也是排好序的，我们可以线性地求出这个数列的逆序数。具体而言，它和归并排序的合并一样，我们不断地比较两个数列当前的较小值，如果较小值出现在 $q$，说明这个数字和 $p$ 中剩下的数字都能组成逆序对，如果使用前面归并排序的伪代码里的变量说明，就是一共组成了 $mid-i+1$ 个逆序对。

但是输入的数列不可以总是可以分成两个有序数列 $p,q$ 的。但是注意到，我们这个计算，相当于计算的是 $p,q$ 之间产生的逆对数（也就是下标 $i$ 对应的数在 $p$ 中，下标 $j$ 对应的数在 $q$ 中的逆序对 $(i,j)$ 个数），剩下的问题就是，如何计算 $p,q$ 内部分别的逆序数。这是可以递归解决的。

最终的算法会和归并排序一样：

1. 将原数列分成两个数列。
2. 分别求解两个数列的逆序对数，并排好序（1,2 步形成递归）。
3. 求解两个数列之间产生的逆序数，同时将两个数列合并。

时间复杂度自然和归并排序相同，是 $\mathcal O(n\log n)$ 的。

桶排序和基数排序

下面是两个比较特殊的排序。这种排序是基于数值进行的，所以只适用于对自然数数列或类似情况进行的排序。如果排序对象为实数列，虽然能写，但是会异常麻烦。

在这一个小节中，我们假定需要排序的数列里的数都是不超过 $M$ 的正整数。

桶排序是一个非常好理解的排序：具体流程为：

1. 建立一个和 $M$ 大小相当的数组 $cnt$（也被叫做“桶”），初始的时候全是 $0$，用于统计每个数字出现的次数。
2. 统计数列每个数字出现的次数。
3. 开一个答案数组，初始为空。从 $1$ 到 $M$ 遍历 $cnt$ 数组，则数字 $i$ 有 $cnt_i$ 个，所以直接在答案数组后面追加 $cnt_i$ 个 $i$ 即可。

正确性非常好理解。时间复杂度和空间复杂度都是 $\mathcal O(n+M)$ 的，所以值域一大你就寄飞了。

于是乎，为了中和桶排序带来的和值域线性相关的巨大复杂度，就有了基数排序。

基数排序的关键在于，我们究竟如何比较两个数的大小的：

1. 如果两个数字位数不同，位数小的那个更小。这一点也可以通过给位数小的数高位补零来对其两个数位数的方式解决。
2. 位数相同时，比较最高位的数字，如果最高位数字相同，比较次高位，若还是相同，继续比较下一位……以此类推。

那么，用这种思想来想象一下排好序的数组是啥：可以想象先把所有数字补位补到位数相同，然后按最高位数字为第一关键字排序，最高位相同则按次高位为第二关键字排序……

如何按照某一个关键字排序呢？注意到，一个关键字的取值，也就是任意数的某一位上的数字，只有可能是 $0\sim 9$ 之间的整数，总共也才 $10$ 个。所以我们完全可以开桶来解决这个事情。

具体地说，我们开 $10$ 个数组 $t_0,t_1,\ldots,t_9$. 然后把每个数字按照当前正在考虑的数位是多少，放到这些数组里，然后 $t_0+t_1+\ldots+t_9$ 就是按这一位排好的结果。

然而这会产生一定的问题：假设我先按最高位排好序了，再按次高位排序的时候，按最高位排序的结果不久被打乱了吗？

于是我们不应该正着来，而是反其道而行之：我们第一步按最低位排序，将得到的结果按次低位排序。我们考虑这样排出来结果是什么：因为次低位是最后排序的，所以最终得到的数列会优先按次低位排序，次低位相同的时候，就是按最低位排的序了。所以要把它从最低位往最高位排序才能得到正确的数列。

在下面的程序中，我们先计算数列的最大数 $M$，然后根据 $M$ 计算每个数的位数 $d$，然后就可以从最低位到最高位依次桶排序了. 程序中 $x$ 代表的是 $a_j$ 的第 $i$ 位的数（通过简单推一下可以得到 $x=\left\lfloor\frac{a_j}{10^{i-1}}\right\rfloor\bmod 10$，$\bmod$ 表示取模运算，即取余数）。

时间复杂度是 $\mathcal O(nd)$ 的，也就是 $\mathcal O(n\log_{10} M)$.