basic_algorithm（复刻版）

tsqtsqtsq0309 · 2023-09-27 08:25:04 · 算法·理论

basic_algorithm（复刻版）

by cssyz tsqtsqtsq

1 前言

基础算法是 OI 中的内容，一方面，这些内容可以让初学者对 OI 的一些思想有初步的认识；另一方面，本章介绍的大部分算法还会在以后的进阶内容中得到运用。因此，掌握好基础算法是非常重要的。

2 模拟

2.1 简介

自然界和日常生活中的有些事物，若用计算机很难建立起枚举、贪心等算法，甚至没法建立数学模型。我们解决这类问题可用模拟法。所谓模拟法，就是用计算机模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起的过程状态的变化，然后从中得出解答。

2.2 技巧

写模拟题时，遵循以下的建议有可能会提升做题速度：

​ 1，在动手写代码之前，在草纸上尽可能地写好要实现的流程。

​ 2，在代码中，尽量把每个部分模块化，写成函数、结构体或类。

​ 3，对于一些可能重复用到的概念，可以统一转化，方便处理：如，某题给你 "YY-MM-DD 时：分" 把它抽取到一个函数，处理成秒，会减少概念混淆。

​ 4，调试时分块调试。模块化的好处就是可以方便的单独调某一部分。

​ 5，写代码的时候一定要思路清晰，不要想到什么写什么，要按照落在纸上的步骤写。

实际上，上述步骤在解决其它类型的题目时也是很有帮助的。

2.3 例题

2.3.1 洛谷 P3397 地毯

2.3.1.1 链接

P3397

2.3.1.2 分析

这道题的数据 n,m\le 1000，规模不大，考虑直接采用模拟算法，每读入一组数据时直接将对应坐标 +1 ，最后再输出就是最终答案。

2.3.2 洛谷 P1601 A+B Problem（高精）

2.3.2.1 链接

P1601

2.3.2.2 分析

高精度板子，相信大家都会。

2.3.3 洛谷 P7075 [CSP-S2020] 儒略日

2.3.3.1 链接

P7075

2.3.3.2 分析

一道非常好(e)玩(xin)的模拟题～。

2.3.4 洛谷 P3397 [SDOI2010] 猪国杀

2.3.4.1 链接

P2482

2.3.4.2 分析

一道非常有意思的模拟题～。

2.4 小结

由于模拟法往往是从实际工程应用中提取出来的一些核心问题，或者本身就是某个工程的简化模型，所以解答模拟题特别需要有良好的理解能力、分析能力和规划能力。模拟题的算法一般都不太复杂，关键是所有条件都不能遗漏并要把条件分析清楚。求解模拟题一般都比较繁琐，编程前一定要预先规划好各个模块的功能和结构，以免具体编程时注意了局部而遗漏了某些重要的方面。

3 枚举

3.1 简介

枚举法的本质就是从所有候选答案中寻找正确的答案。其核心思想就是枚举所有的可能，不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。

3.2 要点

3.2.1 给出解空间

建立简洁的数学模型。

枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？

3.2.2 减少枚举的空间

枚举的范围是什么？是所有的内容都需要枚举吗？

在用枚举法解决问题的时候，一定要想清楚这两件事，否则会带来不必要的时间开销。

3.2.3 选择合适的枚举顺序

根据题目判断。比如例题中要求的是最大的符合条件的素数，那自然是从大到小枚举比较合适。

3.3 优缺点

优点：算法简单，在局部地方使用枚举法，效果十分好。

缺点：运算量过大，当问题的规模变大的时候，循环的阶数越大，执行速度越慢。

3.4 例题

3.4.1 洛谷 P2089 烤鸡

3.4.1.1 链接

P2089

3.4.1.2 分析

数据范围不大，方法很简单，就是直接进行暴力枚举，因为每一种调料只会放 1 到 3 克，而 n \leq 5000，暴力枚举可以通过本题。

3.4.1 洛谷 P8865 [NOIP2022] 种花

3.4.1.1 链接

P8865

3.4.1.2 分析

简简单单的枚举题，只要拆分一下图案再考虑每一部分的贡献即可。然而还是推错式子怒挂 94 pts（我是废物 qwq）。

具体分析：

数据范围 10^3 , O(n^2) 可过.

C

考虑将字母进行拆分并枚举左下角，分别枚举下面的横边以及上面的竖边和横边，设 downc_{i,j} 为点 (i,j) 右侧合法的横边方案数，则有：

由于两条横线长度可以不一致，因此在枚举上面的竖边和横边时可以先枚举竖边再加上横边. 设 upc_{i,j} 为点 (i,j) 上侧合法的横边和竖边方案数，则有：

最后将方案数乘起来就能得到某一点作为左下角时的方案数，将每一点方案数相加可得：

F

分析可知 F 方案数可以在 C 方案数基础上进行枚举，考虑将 F 拆分为 C 和下面的一条短竖，只需再对下面短竖单独进行枚举.设 downf_{i,j} 为点 (i,j) 下侧合法的竖边方案数，则有：

总方案数与 C 同理：

最后暴力枚举每个点的方案数即可。

总时间复杂度 O(tmn).

亿点点小细节：

1.开long long

2.数组清空

3.5 小结

枚举法实现较为简单，在数据范围较小的情况下运行效果十分理想，但在数据范围较大的情况下执行效率较低，容易造成代码运行超过时间限制。在实际应用中应根据不同场景和数据规模合理选择适合的算法。

4 递推

4.1 简介

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

4.2 要点

无论顺推还是逆推，其关键是要找到递推式。

先来浅浅地举个例子：楼梯有 n 阶，上楼可以一步上一阶，也可以一步上二阶。编一个程序，计算共有多少种不同的走法。

这个问题咋一看很复杂，但其实只要找到其中存在的递推关系（即递推式），问题便能够迎刃而解。

在这个问题中，我们从头开始分析：

设 f(n) 表示上 n 阶楼梯的走法数量。

当 n=1 时，有且仅有一种走法为一步上一阶，即 f(1)=1。

当 n=2 时，可以一步上一阶走两次，也可以一步上两阶走一次，即 f(2)=2。

当 n=3 时，我们可以发现，如果要走到第三阶，则必然要先走到第二阶或者第一阶，所以上 3 阶楼梯地走法数量为上 2 阶楼梯的走法数量与上 1 阶楼梯的走法数量之和，即 f(3)=f(2)+f(1)\Rightarrow f(3)=3。

依据这个结论我们可以浅浅地推广一下：对于第 n 阶，从第 n-1 阶走一步跨到第 n 阶，也可以从第 n-2 阶走一步跨到第 n 阶，所以上 n 阶楼梯的走法数量为上 n-1 阶楼梯的走法数量与上 n-2 阶楼梯的走法数量之和，即：f(n)=f(n-1)+f(n-2)。由此我们可以得出递推式：

得到了递推式，我们便可以愉快地写代码了~。

int f[MAXN];
f[1] = 1;
f[2] = 2;
for(int i = 3 ; i <= n ; i ++)
    f[i] = f[i - 1] + f[i - 2];

4.3 几种典型的递推关系

4.3.1 斐波那契数列

斐波那契数列的第一项和第二项都是 1，从第三项开始，每一项都等于前两项之和。通过定义可知，斐波那契数列的第一项和第二项都是确定的，而对于之后的每一项都是由前两项推导而来。易得递推式：

4.3.2 Hanoi 塔问题

问题的提出：Hanoi 塔由 n 个大小不同的圆盘和三根木柱 a,b,c 组成。开始时，这 n 个圆盘由大到小依次套在 a 柱上，如图所示。

要求把 a 柱上 n 个圆盘按下述规则移到 c 柱上：

​ (1) 一次只能移一个圆盘；

(2) 圆盘只能在三个柱上存放；

(3) 在移动过程中，不允许大盘压小盘。

问将这 n 个盘子从 a 柱移动到 c 柱上，总计需要移动多少个盘次？

思路：

设 f(n) 为 n 个盘子从 a 柱移到 c 柱所需移动的盘次。

显然，当 n=1 时，只需把 a 柱上的盘子直接移动到 c 柱就可以了，故 f(1)=1。

当 n = 2 时，先将 a 柱上面的小盘子移动到 b 柱上去；然后将大盘子从 a 柱移到 c 柱,最后，将 b 柱上的小盘子移到 c 柱上，共记 3 个盘次，故 f(2)=3。

以此类推，当 a 柱上有 n 个盘子时，总是先借助 c 柱把上面的 n-1 个盘子移动到 b 柱上，然后把 a 柱最下面的盘子移动到 c 柱上，再借助 a 柱把 b 柱上的 n-1 个盘子移动到 c 柱上；总共移动 f(n-1)+1+f(n-1) 个盘次。

易得递推式：

4.3.3 平面分割问题

问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。

思路：

设 f(n) 为 n 条封闭曲线把平面分割成的区域个数。

由图可知 f(2)-f(1)=2,f(3)-f(2)=4,f(4)-f(3)=6 。

从这些式子中可以看出 f(n)-f(n-1)=2(n-1) 当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。

下面不妨让我们来试着证明一下。当平面上已有 n-1 条曲线将平面分割成 f(n-1) 个区域后，第 n-1 条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了 n-1 条封闭曲线，且第 n 条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加 2(n-1) 个区域，加上已有的 f(n-1) 个区域，一共有 f(n-1)+2(n-1) 个区域。易得递推式：

4.3.4 卡特兰数

问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把 n 边形拆分成若干三角形，不同的拆分数目用 f(n) 表示，f(n) 即为卡特兰数。例如五边形有如下五种拆分方案，故 f(5)=5。求对于一个任意的凸 n 边形相应的 f(n)。

思路：

设 f(n) 表示凸 n 边形的拆分方案数。

由题可知一个凸 n 边形的任意一边必然是一个三角形的一条边。

再根据“不在同一直线上的三点可以确定一个三角形”可知只需要在 p_2,p_3,……,p_{n-1} 中找到一个点 p_k(1\leq k<n) 与 p_1,p_n 共同构成一个三角形的就将一个凸 n 边形分成了三个不相交的部分。

分别设为 1、2、3。其中区域 3 必然是一个三角形，区域 1 是一个凸 k 边形，区域 2 是一个凸 n-k+1 边形，区域 1 的拆分方案总数是 f(k)，区域 2 的拆分方案总数是 f(n-k+1)。

故包含\triangle p_1p_kp_n 的 n 边形拆分方案总数为 f(k)f(n-k+1) 种。

而 p_k 可以是 p_2,p_3,……,p_{n-1} 中的任意一点。

由加法原理易得递推式：

4.3.5 第二类斯特林数

第二类斯特林数表示将 n 个两两不同的元素划分为 k 个互不区分的非空子集的方案数。

考虑利用组合意义证明。

当插入一个新元素时有两种方案：

​ 将新元素单独放入一个子集，有 {n-1 \brace k-1} 种方案。

​ 将新元素放入一个现有非空子集，有 k{n-1 \brace k} 种方案。

由加法原理易得递推式：

4.4 例题

4.4.1 洛谷 P2437 蜜蜂路线

4.4.1.1 链接

P2437

4.4.1.2 分析

浅浅分析一下便可发现这道题的递推关系与爬楼梯问题大同小异，只需要考虑一下具体循环次数即可。

4.4.2 洛谷 P1044 [NOIP2003 普及组] 栈

4.4.2.1 链接

P1044

4.4.2.7 分析

直接卡特兰数递推即可。

4.4.2 洛谷 P1990 覆盖墙壁

4.4.2.1 链接

P1990

4.4.2.6 分析

1，当这面墙的最后一列被铺满时（如下图所示）。

以这种状态结尾的方案数为 f(n-1)。

2.当这面墙的最后两列被铺满时（如下图所示）。

以这种状态结尾的方案数为 f(n-2)。

对于 L 形的瓷砖我们可以用另一个数组 g(n) 表示铺满前 (n+1)\times2 的墙，但是第 (n+1) 列有一个瓷砖已经被铺过的方案数。

所以下面这种情况的方案数为 g(n-2)（如下图所示）。

同理这一种也是 g(n-2)（如下图所示）。

那么这两个数组应该如何维护呢？

第一种情况是变成一个长方形（如下图所示）。

以这种状态结尾的方案数为 f(n-3)。

第二种情况是加上一块砖后不是长方形（如下图所示）。

以这种状态结尾的方案数为 g(n-3)。

综上所述，易得递推式：

4.5 小结

递推可以使复杂运算转化为简单运算，通常情况下效率较高，但在实际应用场景中他通常是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然其中的某些问题也可以用搜索的方法来完成，但搜索的方法与利用递推关系的方法比较起来效率会变低，时间复杂度也会有所提高。

5 递归

5.1 简介

递归，在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

以下是一些有助于理解递归的例子：

1，什么是递归？

2，如何给一堆数字排序？

​ 答：分成两半，先排左半边再排右半边，最后合并就行了，至于怎么排左边和右边，请重新阅读这句话。

3，你今年几岁？

​ 答：去年的岁数加一岁，1999 年我出生。

递归在数学中非常常见。例如，集合论对自然数的正式定义是：1 是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。

递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。

5.2 特点

结构清晰，可读性强。练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时，递归写多了就能敏锐发现这个特点，进而高效解决问题。

在程序执行中，递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成栈溢出的后果。

显然有时候递归处理是高效的，比如归并排序；有时候是低效的，比如数孙悟空身上的毛，因为堆栈会消耗额外空间，而简单的递推不会消耗空间。

比较初级的递归实现可能递归次数太多，容易超时。这时需要对递归进行优化。

5.3 思想

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

三大要素

1，明确函数功能

首先需要明确递归函数的功能，即：这个函数是用来干嘛的？它要做一件什么样的事，这里以计算斐波那契数列第 n 项为例:

inline int f(int n)
{

}

这个函数的功能就是计算斐波那契数列第 n 项，现在我们已经明确了这个函数该干嘛，接下来看第二要素：

2，寻找边界条件

递归的特点就是在递归函数运行的过程中会调用函数本身，所以必须确定一个边界条件，不然递归函数会一直调用自己无法自行退出，反映到程序运行上就会出现段错误（都怪 \texttt{dyz}）

所以，我们需要知道在什么时候递归结束，之后直接返回结果，但必须注意，这个时候我们必须能根据这个参数直接知道此时应该返回的结果是什么。

还是上面的哪一个例子，先来回顾一下斐波那契数列的递推式：

由递推式可知，当 n=1 或者 n=2 时答案为 1，现在完善一下代码加入第二要素：

inline int f(int n)
{
    if(n == 1 || n == 2)
        return 1;
}

3，找出关系式：

第三要素就是，我们要不断缩小参数的范围，使得缩小之后可以通过一些辅助的变量或者操作，使原函数的结果不变。

还是上面那个例子，f(n) 的范围很大（我知道你很急，但你先别急，你先让我急），但我们由递推式可知，f(n)=f(n-1)+f(n-2)，这样范围就变小了，计算 f(n) 时我们只需要将 f(n-1) 与 f(n-2) 相加即可。

inline int f(int n)
{
    if(n == 1 || n == 2)
        return 1;
    return f(n - 1) + f(n - 2);
}

那么问题来了：f 里面有 f 是怎么一回事呢？

我们可以尝试着画出来：

先递进，再回归——这就是「递归」。

5.4 例题

5.4.1 洛谷 P1464 Function

5.4.1.1 链接

P1464

5.4.1.2 分析

简简单单的递归题，根据题意编写递归函数即可。

5.4.2 洛谷 P1928 外星密码

5.4.2.1 链接

P1928

5.4.1.2 分析

典型的递归问题，遇到中括号直接调用递归函数即可，至于具体实现过程可以用一个栈来维护。

5.5 总结

现在，我们更加相信递归是一种强大的技术，它使我们能够以一种优雅而有效的方式解决许多问题。同时，它也不是解决任务问题的灵丹妙药。由于时间或空间的限制，并不是所有问题都可以用递归解决，在递归过程中可能会出现重复计算、栈溢出等问题，这时我们应当使用适当的优化方法（如记忆化等），在实际应用中应当实际情况实际考虑。

6 排序

6.1 简介

排序算法是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。

6.2 性质

6.2.1 稳定性

稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。

拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 R 和 S，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。

基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。

选择排序、堆排序、快速排序、希尔排序不是稳定排序。

6.2.2 时间复杂度

时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用 O 表示。

简单计算复杂度的方法一般是统计「简单操作」的执行次数，有时候也可以直接数循环的层数来近似估计。

时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。

基于比较的排序算法的时间复杂度下限是 O(n\log n) 的。

当然也有不是 O(n\log n) 的。例如，计数排序 的时间复杂度是 O(n + w)，其中 w 代表输入数据的值域大小。

6.3 选择排序

6.3.1 简介

选择排序是一种简单直观的排序算法。它的工作原理是每次找出第 i 小的元素，然后将这个元素与数组第 i 个位置上的元素交换。

6.3.2 稳定性

由于算法存在交换操作，故该算法是一种不稳定的排序算法。

6.3.3 时间复杂度

选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n^2)。

6.3.4 代码实现

for(int i = 1 ; i < n ; i ++)  
{  
    int tmp = i;  
    for(int j = i + 1 ; j <= n ; j ++)  
        if(a[j] < a[tmp])  
            tmp = j;  
    swap(a[i], a[tmp]);  
}  

6.4 冒泡排序

6.4.1 简介

冒泡排序是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。

6.4.2 稳定性

冒泡排序是一种稳定的排序算法。

6.4.3 时间复杂度

在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 O(n)。在最坏情况下，冒泡排序要执行 \frac{(n-1)n}{2} 次交换操作，时间复杂度为 O(n^2)。

冒泡排序的平均时间复杂度为 O(n^2)。

6.4.4 代码实现

bool flag;  
for(int i = 1 ; i < n ; i ++)
{
    flag = false;
    for(int j = 1 ; j < n ; j ++)
        if(arr[j] > arr[j + 1])
        {
            swap(arr[j], arr[j + 1]);
            flag = true;
        }
    if(flag == false)
        break;
}

6.5 插入排序

6.5.1 简介

插入排序是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。

6.5.2 稳定性

插入排序是一种稳定的排序算法。

6.5.3 时间复杂度

插入排序的最优时间复杂度为 O(n)，在数列几乎有序时效率很高，最坏时间复杂度和平均时间复杂度都为 O(n^2)。

6.5.4 代码实现

for(int i = 2 ; i <= n ; i ++)  
{  
    int tmp = a[i];  
    int j = i - 1;  
    while(j > 0 && a[j] > tmp)  
    {  
        a[j + 1] = a[j];  
        j--;  
    }  
    a[j + 1] = tmp;  
}

6.6 快速排序

6.6.1 简介

快速排序，又称分区交换排序，简称「快排」，是一种被广泛运用的排序算法。

6.6.2 实现

快速排序的工作原理是通过分治的方式来将一个数组排序。

快速排序分为三个过程：

​ 1，将数列划分为两部分（要求保证相对大小关系）；

​ 2，递归到两个子序列中分别进行快速排序；

​ 3，不用合并，因为此时数列已经完全有序。

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 m 来当做两个子数列的分界。

之后，维护一前一后两个指针 p 和 q，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 q 遇到了一个比 m 小的数，那么可以交换 p 和 q 位置上的数，再把 p 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

其实，快速排序没有指定应如何具体实现第一步，不论是选择 m 的过程还是划分的过程，都有不止一种实现方法。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。

6.6.3 稳定性

快速排序是一种不稳定的排序算法。

6.6.4 时间复杂度

快速排序的最优时间复杂度和平均时间复杂度为 O(n\log n)，最坏时间复杂度为 O(n^2)。 对于最优情况，每一次选择的分界值都是序列的中位数，此时算法时间复杂度满足的递推式为 T(n)=2T(\frac{n}{2})+O(n)，由主定理，T(n)=O(nlogn)。 对于最坏情况，每一次选择的分界值都是序列的最值，此时算法时间复杂度满足的递推式为 T(n)=T(n-1)+O(n)，累加可得 T(n)=O(n^2)。 对于平均情况，每一次选择的分界值可以看作是等概率随机的。

6.6.5 代码实现

inline void sort(int l, int r)
{
    int i = l;
    int j = r;
    int base = a[l + r >> 1];
    do
    {
        while(a[i] < base)
            i++;
        While(a[j] > base)
            j--;
        if(i <= j)
        {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    while(i <= j)
    if(l < j)
        sort(1, j);
    if(i < r)
        sort(i, r);
}

6.7 归并排序

6.7.1 简介

归并排序是高效的基于比较的稳定排序算法。

6.7.2 实现

归并排序最核心的部分是合并过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。

从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。

为保证排序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）而非小于时（a[i] < b[j]）就要作为最小值放入 c[k]。

6.7.3 稳定性

归并排序是一种稳定的排序算法。

6.7.4 代码实现

inline void merge_sort(int *a, int l, int r)  
{  
    if (r - l <= 1)  
        return;  
    int mid = l + ((r - l) >> 1);  
    merge_sort(a, l, mid);  
    merge_sort(a, mid, r);  
    int tmp[1024] = {};  
    merge(a + l, a + mid, a + mid, a + r, tmp + l);  
        for(int i = l ; i < r ; i ++)  
    a[i] = tmp[i];  
}  

6.8 堆排序

6.8.1 简介

堆排序是指利用二叉堆这种数据结构所设计的一种排序算法。堆排序的适用数据结构为数组。

6.8.2 实现

首先建立大根堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质

之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质。以此类推，在第 n-1 次操作后，整个数组就完成了排序。

6.8.3 稳定性

堆排序是一种稳定的排序算法。

6.8.4 时间复杂度

堆排序的最优时间复杂度、平均时间复杂度、最坏时间复杂度均为 O(n\log n)。

6.8.5 代码实现

inline void MaxHeapify(int arr[], int start, int end)
{
    int dad = start;
    int son = dad * 2 + 1;
    while(son <= end)
    {
        if(son + 1 <= end && arr[son] < arr[son + 1])
            son++;
        if(arr[dad] > arr[son])
            return;
        else
        {
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

inline void HeapSort(int arr[], int len)
{
    for(int i = len / 2 - 1; i >= 0; i--)
        MaxHeapify(arr, i, len - 1);
    for(int i = len - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        MaxHeapify(arr, 0, i - 1);
    }
}

6.9 计数排序

6.9.1 简介

计数排序是一种线性时间的排序算法。

6.9.2 实现

计数排序的原理是使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数，然后根据数组 C 将 A 中的元素排列到正确的位置。

它的工作过程分为三个步骤：

1. 计算每个数出现了几次；
2. 求出每个数出现次数的前缀和；
3. 利用出现次数的前缀和，从右至左计算每个数的排名。

计算前缀和的原因

直接将 C 中正数对应的元素依次放入 A 中不能解决元素重复的情形。

我们通过为额外数组 C 中的每一项计算前缀和，结合每一项的数值，就可以为重复元素确定一个唯一排名：

额外数组 C 中每一项的数值即是该 key 值下重复元素的个数，而该项的前缀和即是排在最后一个的重复元素的排名。

如果按照 A 的逆序进行排列，那么显然排序后的数组将保持 A 的原序（相同 key 值情况下)，也即得到一种稳定的排序算法。

6.9.3 稳定性

计数排序是一种稳定的排序算法。

6.9.4 时间复杂度

计数排序的时间复杂度为 O(n + w), 其中 w 代表待排序数据值域大小。

6.9.5 代码实现

#define MAXN 100005;
#define MAXW 100005;

int n, w, a[MAXN], cnt[MAXW], b[MAXN];

inline void counting_sort()
{
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1 ; i <= n ; i ++)
        cnt[a[i]]++;
    for(int i = 1 ; i <= w ; i ++)
        cnt[i] += cnt[i - 1];
    for(int i = n ; i >= 1 ; i --)
        b[cnt[a[i]]--] = a[i];
}

6.10 基数排序

6.10.1 简介

基数排序是一种非比较型的排序算法，最早用于解决卡片排序的问题。

6.10.2 实现

基数排序的工作原理是将待排序的元素拆分为 k 个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第 k 关键字进行稳定排序，再对第 k-1 关键字进行稳定排序，再对第 k-2 关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。

6.10.3 稳定性

基数排序是一种稳定的排序算法。

6.10.4 时间复杂度

一般来说，如果每个关键字的值域都不大，就可以使用计数排序作为内层排序，此时的复杂度为 O(kn+\sum_{i=1}^n w_i)，其中 w_i 为第 i 关键字的值域大小。如果关键字值域很大，就可以直接使用基于比较的 O(nk\log n) 排序而无需使用基数排序了。

6.10.5 代码实现

#define MAXN 100005
#define MAXW 100005
#define MAXK 105

int n, w[MAXK], k, cnt[MAXW];
struct element
{
    int key[MAXK];
    bool operator<(const element &y) const
    {
        for(int i = 1 ; i <= k ; i ++)
        {
            if(key[i] == y.key[i])
                continue;
            return key[i] < y.key[i];
        }
        return false;
    }
}a[MAXN], b[MAXN];

inline void counting_sort(int p)
{
    for(int i = 0 ; i < MAXW ; i ++)
        cnt[i] = 0;
    for(int i = 1 ; i <= n ; i ++)
        cnt[a[i].key[p]]++;
    for(int i = 1 ; i <= w[p] ; i ++)
        cnt[i] += cnt[i - 1];
    for(int i = n ; i >= 1 ; i --)
            b[cnt[a[i].key[p]]--] = a[i];
    memcpy(a, b, sizeof(a));
}

inline void radix_sort()
{
    for(int i = k ; i >= 1 ; i --)
            counting_sort(i);
}

6.11 桶排序

6.11.1 简介

桶排序是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。

6.11.2 实现

桶排序按下列步骤进行：

1. 设置一个定量的数组当作空桶；
2. 遍历序列，并将元素一个个放到对应的桶中；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把元素再放回原来的序列中。

6.11.3 稳定性

桶排序是一种稳定的排序算法。

6.11.4 时间复杂度

桶排序的平均时间复杂度为 O(n+n^2/k+k) （将值域分成 n 块 + 排序 + 合并），当 k\approx n 时为 O(n),最坏时间复杂度为 O(n^2)。

6.11.5 代码实现

#define MAXN 100005
int n, w, a[MAXN];
vector<int> bucket[MAXN];

inline void insertion_sort(vector<int> &a)
{
    for(int i = 1 ; i < a.size() ; i ++)
    {
        int key = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

inline void bucket_sort()
{
    nit siz = w / n + 1;
    for(int i = 0 ; i < n ; i ++)
            bucket[i].clear();
    for(int i = 1 ; i <= n ; i ++)
        bucket[a[i] / bucket_size].push_back(a[i]);
    int p = 0;
    for(int i = 0 ;i < n ; i ++)
    {
        insertion_sort(bucket[i]);
        for(int j = 0 ; j < bucket[i].size() ; j ++)
                a[++p] = bucket[i][j];
    }
}

6.12 希尔排序

6.12.1 简介

希尔排序，也称为缩小增量排序法，是插入排序的一种改进版本。希尔排序以它的发明者希尔命名。

6.12.2 实现

排序对不相邻的记录进行比较和移动：

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2. 对这些子序列进行插入排序；
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。

6.12.3 稳定性

希尔排序是一种不稳定的排序算法。

6.12.4 时间复杂度

希尔排序的最优时间复杂度为 O(n)，平均时间复杂度和最坏时间复杂度与间距序列的选取（就是间距如何减小到 1）有关，比如「间距每次除以 3」的希尔排序的时间复杂度是 O(n^{3/2})。已知最好的最坏时间复杂度为 O(n\log^2n)。

6.12.5 代码实现

inline void shell_sort(int array[], int length)
{
    int h = 1;
    while (h < length / 3)
        h = 3 * h + 1;
    while(h >= 1)
        for(int i = h ; i < length ; i++)
            for(int j = i ; j >= h && array[j] < array[j - h] ; j -= h)
                swap(array[j], array[j - h]);
    h /= 3;
}

6.13 锦标赛排序

6.13.1 简介

锦标赛排序，又被称为树形选择排序，是选择排序的优化版本，堆排序的一种变体（均采用完全二叉树）。它在选择排序的基础上使用优先队列查找下一个该选择的元素。

锦标赛排序的名字来源于单败淘汰制的竞赛形式。在这种赛制中有许多选手参与比赛，他们两两比较，胜者进入下一轮比赛。这种淘汰方式能够决定最好的选手，但是在最后一轮比赛中被淘汰的选手不一定是第二好的——他可能不如先前被淘汰的选手。

6.13.2 实现

以最小锦标赛排序树为例：

待排序元素是叶子节点显示的元素。红色边显示的是每一轮比较中较小的元素的胜出路径。显然，完成一次＂锦标赛＂可以选出一组元素中最小的那一个。

每一轮对 n 个元素进行比较后可以得到 \frac{n}{2} 个「优胜者」，每一对中较小的元素进入下一轮比较。如果无法凑齐一对元素，那么这个元素直接进入下一轮的比较。

完成一次「锦标赛」后需要将被选出的元素去除。直接将其设置为 \infty（这个操作类似堆排序)，然后再次举行「锦标赛」选出次小的元素。

之后一直重复这个操作，直至所有元素有序。

6.13.3 稳定性

锦标赛排序是一种不稳定的排序算法。

6.13.4 时间复杂度

锦标赛排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O(n\log n)。它用 O(n) 的时间初始化「锦标赛」，然后用 O(\log n) 的时间从 n 个元素中选取一个元素。

6.13.5 代码实现

#define MAXN 100005

int n, a[MAXN], tmp[MAXN << 1];

inline int winner(int pos1, int pos2)
{
    int u = pos1 >= n ? pos1 : tmp[pos1];
    int v = pos2 >= n ? pos2 : tmp[pos2];
    if(tmp[u] <= tmp[v])
        return u;
    return v;
}

inline void creat_tree(int &value)
{
      for(int i = 0 ; i < n ; i ++)
          tmp[n + i] = a[i];
      for(int i = 2 * n - 1; i > 1; i -= 2)
      {
            int k = i / 2;
            int j = i - 1;
            tmp[k] = winner(i, j);
      }
      value = tmp[tmp[1]];
      tmp[tmp[1]] = INF;
}

inline void recreat(int &value)
{
    int i = tmp[1];
    while (i > 1)
    {
        int j;
        int k = i / 2;
        if(i % 2 == 0 && i < 2 * n - 1)
            j = i + 1;
        else
            j = i - 1;
        tmp[k] = winner(i, j);
        i = k;
    }
    value = tmp[tmp[1]];
    tmp[tmp[1]] = INF;
}

inline void tournament_sort()
{
    int value;
    creat_tree(value);
    for(int i = 0; i < n; i++)
    {
        a[i] = value;
        recreat(value);
    }
}

7 位运算

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共 6 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

7.1 按位与、按位或、按位异或

按位异或运算的逆运算是其本身，也就是说，一个数两次按位异或的结果是其本身，即：

应用：在不借助临时变量的情况下交换两个变量的值。

a ^= b ^= a ^= b;

7.2 按位取反

按位取反是对一个数进行的运算，即单目运算。

其作用为将一个数对应二进制中 0 和 1 全部取反（即 1 变 0，0 变 1）。

7.3 左移和右移

3. 复杂度 O(1)

9 参考文献

递归详解——让你真正明白递归的含义

算法讲解之递推算法

递推与递归

OI Wiki

C++ STL 总结-基于算法竞赛（悠享版）

洛谷