0x05 排序

在程序设计中，通常会使用到以下这些排序算法，这里把它们分为三类：

1. 选择排序、插入排序、冒泡排序

2. 堆排序、归并排序、快速排序

3. 计数排序、基数排序、桶排序

前两类是基于比较的排序算法，对 $n$ 个元素进行排序时，若元素比较大小的时间复杂度为0(1)，则第一类排序算法的时间复杂度为 $O(n^{2})$ ，第二类排序算法的时间复杂度为 $O(n\log n)$ 。实际上，基于比较的排序算法的时间复杂度下界为 $O(n\log n)$ ，因此堆排序、归并排序与快速排序已经是时间复杂度最优的基于比较的排序算法。

第三类算法换了一种思路，它们不直接比较大小，而是对被排序的数值采取按位划分、分类映射等处理方式，其时间复杂度不仅与 $n$ 有关，还与数值的大小范围 $m$ 有关。读者很容易在各种算法书籍或网络上找到这些排序算法的讲解与实现，这里就不再赘述，请读者自行学习理解。讨论这些排序算法的应用并以它们作为工具去解决问题才是我们的重点。

离散化

排序算法的第一个应用是离散化。通俗地讲，“离散化”就是把无穷大集合中的若干个元素映射为有限集合以便于统计的方法。例如在很多情况下，问题的范围虽然定义在整数集合 $\mathbb{Z}$ ，但是只涉及其中 $m$ 个有限数值，并且与数值的绝对大小无关（只把这些数值作为代表，或只与它们的相对顺序有关）。此时，我们就可以把整数集合 $\mathbb{Z}$ 中的这 $m$ 个整数与 $1 \sim m$ 建立映射关系。如果有一个时间、空间复杂度与数值范围 $\mathbb{Z}$ 的大小有关的算法，在离散化后，该算法的时间、空间复杂度就降低为与 $m$ 相关。

具体地说，假设问题涉及int范围内的 $n$ 个整数 $a[1] \sim a[n]$ ，这 $n$ 个整数可能有重复，去重以后共有 $m$ 个整数。我们要把每个整数 $a[i]$ 用一个 $1 \sim m$ 之间的整数代替，并且保持大小顺序不变，即如果 $a[i]$ 小于（或等于、大于） $a[j]$ ，那么代替 $a[i]$ 的整数也小于（或等于、大于）代替 $a[j]$ 的整数。

很简单，我们可以把 $a$ 数组排序并去掉重复的数值，得到有序数组 $b[1] \sim b[m]$ ，在 $b$ 数组的下标 $i$ 与数值 $b[i]$ 之间建立映射关系。若要查询整数 $i (1 \leq i \leq m)$ 代替的数值，只需直接返回 $b[i]$ ；若要查询整数 $a[j] (1 \leq j \leq n)$ 被哪个 $1 \sim m$ 之间的整数代替，只需在数组 $b$ 中二分查找 $a[j]$ 的位置即可。

void discrete(){//离散化sort(a+1，a+n+1);for(inti=1；i<=n；i++)//也可用STL中的unique函数if（i==1||a[i] != a[i-1])b[++m]=a[i];  
}  
void query(intx){//查询  $\mathbf{x}$  映射为哪个  $1\sim m$  之间的整数return lower_bound(b+1,b+m+1,x)-b;

【例题】Cinema Codeforces 670C

有 $m$ 部正在上映的电影，每部电影的语音和字幕都采用不同的语言，用一个 int 范围内的整数来表示语言。有 $n$ 个人相约一起去看其中一部电影，每个人只会一种语言，如果一个人能听懂电影的语音，他会很高兴；如果能看懂字幕，他会比较高兴；如果语音和字幕都不懂，他会不开心。请你选择一部电影让这 $n$ 个人一起看，使很高兴的人最多。若答案不唯一，则在此前提下再让比较高兴的人最多， $n, m \leq 2 * 10^5$ 。

虽然语言的范围在 int 以内，但是这 $m$ 部电影与 $n$ 个人最多涉及 $2 * m + n$ 种语言。我们把所有电影和人涉及的语言放进一个数组，排序并离散化，用一个 $1 \sim 2 * m + n$ 之间的整数代替每种语言。此时我们就可以用数组直接统计会上述每种语言的人的数量，从而选择满足题目要求的电影。时间复杂度为 $O\big((n + m) \log (n + m)\big)$ 。

$\spadesuit$ 中位数

在有序序列中，中位数具有一些很优美的性质，可以引出一系列与它相关的问题。动态维护序列的中位数也非常值得探讨。我们通过几道例题来感受中位数的相关应用。

【例题】货仓选址

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A[1] \sim A[N]$ 。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

把 $A[1] \sim A[N]$ 排序，设货仓建在 $X$ 坐标处， $X$ 左侧的商店有 $P$ 家，右侧的商店有 $Q$ 家。若 $P < Q$ ，则每把货仓的选址向右移动 1 单位距离，距离之和就会变小 $Q - P$ 。同理，若 $P > Q$ ，则货仓的选址向左移动会使距离之和变小。当 $P = Q$ 时为最优解。

因此货仓应该建在中位数处，即把 $A$ 排序后，当 $N$ 为奇数时，货仓建在 $A[(N + 1)/2]$ 处最优；当 $N$ 为偶数时，货仓建在 $A[N/2] \sim A[N/2 + 1]$ 之间的任何位置都是最优解。

【例题】七夕祭 BZOJ3032/CODEVS2485

七夕节因牛郎织女的传说而被扣上了“情人节”的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。矩形的祭典会场由 $N$ 行 $M$ 列共计 $N * M$ 个摊点组成。虽然摊点种类繁多,不过 cl 只对其中的 $T$ 个摊点感兴趣,比如章鱼烧、

苹果糖、棉花糖、射的屋什么的。Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。

不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当它们处在同一行或者同一列的相邻位置上。因为zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。 $1 \leq N, M \leq 10^{5}$ ， $0 \leq T \leq min(N * M, 10^{5})$ 。

经过分析我们可以发现，交换左右两个相邻的摊点只会改变某两列中cl感兴趣的摊点数，不会改变每行中cl感兴趣的摊点数。同理，交换上下两个相邻的摊点只会改变某两行中cl感兴趣的摊点数，不会改变每列中cl感兴趣的摊点数。所以我们可以把本题分成两个互相独立的部分计算：

1. 通过最少次数的左右交换使每列中cl感兴趣的摊点数相同。

2. 通过最少次数的上下交换使每行中 cl 感兴趣的摊点数相同。

以第1个问题为例进行探讨。

我们可以统计出在初始情况下，每列中cl感兴趣的摊点总数，记为 $C[1]\sim C[M]$ 。若cl感兴趣的摊点总数 $T$ 不能被 $M$ 整除，则不可能达到要求。若 $T$ 能被 $M$ 整除，则我们的目标就是让每列中有 $T / M$ 个cl感兴趣的摊点。

思考到这里，读者可能已经想到了一个与此类似的经典问题“均分纸牌”。“均分纸牌”问题是说，有 $M$ 个人排成一行，他们手中分别有 $C[1] \sim C[M]$ 张纸牌，在每一步操作中，可以让某个人把自己手中的一张纸牌交给他旁边的一个人，求至少需要多少步操作才能让每个人手中持有的纸牌数相等。

显然，“均分纸牌”问题当所有人手中持有的纸牌总数 $T$ 能被 $M$ 整除时有解，在有解时，我们可以先考虑第一个人：

1. 若 $C[1] > T / M$ ，则第一个人需要给第二个人 $C[1] - T / M$ 张纸牌，即把 $C[2]$ 加上 $C[1] - T / M$ 。

2. 若 $C[1] < T / M$ ，则第一个人需要从第二个人手中拿 $T / M - C[1]$ 张纸牌，即把 $C[2]$ 减去 $T / M - C[1]$ 。

我们按照同样的方法依次考虑第 $2 \sim M$ 个人。即使在某个时刻有某个 $C[i]$ 被减为负数也没有关系，因为接下来 $C[i]$ 就会从 $C[i + 1]$ 处拿牌，在实际中可以认为 $C[i]$ 从 $C[i + 1]$ 处拿牌发生在 $C[i - 1]$ 从 $C[i]$ 处拿牌之前。按照这种方法，经过计算，达到目标所需要的最少步数其实就是：

$\sum_{i=1}^{M}\left|i*\frac{T}{M}-G[i]\right|$ ，其中 $G$ 是 $C$ 的前缀和，即 $G[i]=\sum_{j=1}^{i}C[j]$

其含义是每个“前缀”最初共持有 $G[i]$ 张纸牌，最终会持有 $i * T / M$ 张纸牌，多退少补，会与后边的人发生“二者之差的绝对值”张纸牌的交换。

如果我们设 $A[i] = C[i] - T / M$ ，即一开始就让每个人手中的纸牌数都减掉 $T / M$ 并且最终让每个人手里都恰好有0张纸牌，答案显然不变，就是：

$\sum_{i=1}^{M}|S[i]|$ ，其中 $S$ 是 $A$ 的前缀和，即 $S[i] = \sum_{j=1}^{i} A[j]$

从数学的角度，以上两个公式也可以互相推导得到。

回到本题，如果不考虑“第1列与最后一列也是相邻的”这一条件，那么刚才提到的本题中的第1个问题与“均分纸牌”问题是等价的。若问题有解，一定存在一种适当的顺序，使得每一步传递纸牌的操作可以转化为交换一对左右相邻的摊点（其中cl恰好对这两个摊点之一感兴趣）。

若第1列与最后一列相邻，则问题等价于一个“环形均分纸牌”。仔细思考可以发现，一定存在一种最优解的方案，环上某两个相邻的人之间没有发生纸牌交换操作。于是有一种朴素的做法是，枚举这个没有发生交换的位置，把环断开看成一行，转化为一般的“均分纸牌”问题进行计算。

首先，一般的“均分纸牌”问题就相当于在第 $M$ 个人与第1个人之间把环断开，此时这 $M$ 个人写成一行，其持有的纸牌数、前缀和分别是：

如果在第 $k$ 个人之后把环断开写成一行，这 $M$ 个人持有的纸牌数、前缀和分别是：

注意此处 $A$ 是减去最终每个人手里纸牌数 $T / M$ 之后的数组， $A$ 数组均分之后每个人手里都有0张纸牌，所以 $S[M] = 0$ 。也就是说，从第 $k$ 个人把环断开写成一行，前缀和数组的变化是每个位置都减掉 $S[k]$ ！

根据我们上面推导的公式，所需最少步数为：

当 $k$ 取何值时上式最小？这就是上一题“货仓选址”！其中 $S[i]$ 是数轴上 $M$ 家商店的位置， $S[k]$ 是货仓的位置， $|S[i] - S[k]|$ 就是二者之间的距离。根本不需要枚举 $k$ ，只需要把 $S$ 从小到大排序，取中位数作为 $S[k]$ 就是最优解！至此，本题得到完美解决，时间复杂度为 $\mathcal{O}(N \log N + M \log M)$ 。

综上所述，本题可类比为行、列方向上的两次“环形均分纸牌”问题。环形均分纸牌又类比为“均分纸牌”与“货仓选址”问题。其中的每一步都仅使用了基本算法和性质，最后转化为了简单而经典的问题。读者应该时刻把各种模型之间的简化、扩展和联系作为算法学习与设计的脉络，以点成线，触类旁通，才能产生数量到质量的飞跃。

【例题】RunningMedian POJ3784

动态维护中位数问题：依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

本题有两种做法，使用“对顶堆”的在线做法（读入的同时即时计算答案）和使用“链表+Hash”的离线做法（完成所有读入后进行计算然后再统一输出）。后者将在第0x13节“链表与邻接表”中讲解。另外，我们将在第0x17节详细讨论“二叉堆”，对其概念不熟悉的读者可以先进行学习。

为了动态维护中位数，我们可以建立两个二叉堆：一个小根堆、一个大根堆。在依次读入这个整数序列的过程中，设当前序列长度为 $M$ ，我们始终保持：

1. 序列中从小到大排名为 $1 \sim M / 2$ 的整数存储在大根堆中；

2. 序列中从小到大排名为 $M / 2 + 1 \sim M$ 的整数存储在小根堆中。

任何时候，如果某一个堆中元素个数过多，打破了这个性质，就取出该堆的堆顶插入另一个堆。这样一来，序列的中位数就是小根堆的堆顶。

每次新读入一个数值 $X$ 后，若 $X$ 比中位数小，则插入大根堆，否则插入小根堆，在插入之后检查并维护上述性质即可。这就是“对顶堆”算法。

$\spadesuit$ 第 $k$ 大数

给定 $n$ 个整数，如何求出第 $k$ 大的数？我们当然可以直接对这 $n$ 个整数进行快速排序，然后输出从大到小排在第 $k$ 个的数，时间复杂度为 $O(n \log n)$ 。实际上利用类似于快速排序的思想，只需要 $O(n)$ 的时间即可求出第 $k$ 大数。

从大到小进行快速排序算法的思想是，在每一层递归中，随机选取一个数为基准，把比它大的数交换到“左半段”，把其余的数和基准值自身一起作为“右半段”，然后

继续递归对左右两边分别进行排序，在平均情况下快速排序的复杂度为 $O(n\log n)^{1}$ 。

实际上在每次选取基准值后，我们可以统计出大于基准值的数的数量 $cnt$ ，如果 $k \leq cnt$ ，我们就在左半段（比基准值大的数中）寻找第 $k$ 大数；如果 $k > cnt$ ，我们就在右半段（小于或等于基准值的数中）寻找第 $k - cnt$ 大数。因此寻找第 $k$ 大数时，我们只需要进入左右两半二者之一继续递归，在平均情况下复杂度为 $n + n / 2 + n / 4 + \dots + 1 = 0(n)$ 。

$\spadesuit$ 逆序对

对于一个序列 $a$ ，若 $i < j$ 且 $a[i] > a[j]$ ，则称 $a[i]$ 与 $a[j]$ 构成逆序对。

使用归并排序可以在 $O(n \log n)$ 的时间里求出一个长度为 $n$ 的序列中逆序对的个数。归并排序每次把序列二分，递归对左右两半排序，然后合并两个有序序列。

递归对左右两半排序时，可以把左右两半各自内部的逆序对数作为子问题计算，因此我们只需要在合并时考虑“左边一半里一个较大的数”与“右边一半里一个较小的数”构成逆序对的情形，求出这种情形的个数。

合并两个有序序列 $a[l \sim mid]$ 与 $a[mid + 1 \sim r]$ 可以采用两个指针 $i$ 与 $j$ 分别对二者进行扫描的方式，不断比较两个指针所指向数值 $a[i]$ 和 $a[j]$ 的大小，将小的那个加入到排序的结果数组中。若小的那个是 $a[j]$ ，则 $a[i \sim mid]$ 都比 $a[j]$ 要大，它们都会与 $a[j]$ 构成逆序对，可以顺便统计到答案中。

void merge(int l, int mid, int r) {
    // 合并 a[l~mid] 与 a[mid+1~r]
    // a 是待排序数组，b 是临时数组，cnt 是逆序对个数
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) 
        if (j > r || i <= mid && a[i] < a[j]) b[k] = a[i++] 
            else b[k] = a[j++] , cnt += mid - i + 1;
    for (int k = l; k <= r; k++) a[k] = b[k];
}

求逆序对的常用方法还有树状数组，我们将在后续的章节中讲解树状数组的应用。

【例题】Ultra-QuickSort POJ2299

给定一个长度为 $n(n \leq 5 * 10^5)$ 的序列 $a$ ，如果只允许进行比较和交换相邻两个

数的操作，求至少需要多少次交换才能把 $a$ 从小到大排序。

只通过比较和交换相邻两个数值的排序方法，实际上就是冒泡排序算法。在排序过程中每找到一对大小颠倒的相邻数值，把它们交换，就会使整个序列的逆序对个数减少1。最终排好序后逆序对个数显然为0，所以对 $a$ 进行冒泡排序需要的最少交换次数就是序列 $a$ 中逆序对的个数。我们直接使用归并排序求出 $a$ 的逆序对数就是本题的答案。

【例题】奇数码问题

你一定玩过八数码游戏，它实际上是在一个 $3*3$ 的网格中进行的，1个空格和 $1\sim 8$ 这8个数字恰好不重不漏地分布在这 $3*3$ 的网格中。

528
13
467

在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。

例如在上例中，空格可与左、上、下面的数字交换，分别变成：

奇数码游戏是它的一个扩展，在一个 $n*n$ 的网格中进行，其中 $n$ 为奇数，1个空格和 $1 \sim n * n - 1$ 这 $n * n - 1$ 个数恰好不重不漏地分布在 $n * n$ 的网格中。空格移动的规则与八数码游戏相同，实际上，八数码就是一个 $n = 3$ 的奇数码游戏。

现在给定两个奇数码游戏的局面, 请判断是否存在一种移动空格的方式, 使得其中一个局面可以变化到另一个局面。奇整数 $3 \leq n \leq 500$ 。

扩展题目：POJ2893 M × N Puzzle

奇数码游戏两个局面可达，当且仅当两个局面下网格中的数依次写成1行 $n*n-1$ 个元素的序列后（不考虑空格），逆序对个数的奇偶性相同。例如题目描述中的第一个局面写成[52813467]。该结论的必要性很容易证明：空格左右移动时，写成的序列显然不变；空格向上（下）移动时，相当于某个数与它后（前）边的 $n-1$ 个数交换了位置，因为 $n-1$ 是偶数，所以逆序对数的变化也只能是偶数。该结论的充分性证明较为复杂，我们将不在此大篇幅讨论这样一个数学问题。

上面的结论还可以扩展到 $n$ 为偶数的情况，此时两个局面可达当且仅当两个局面对应网格写成序列后，“逆序对个数 + 两个局面下空格之间的行数之差”的奇偶性相

同。事实上，在 $n * m$ 网格上 $(n, m \geq 2)$ 也服从上述两个结论之一（根据列数奇偶性分情况讨论）。

总而言之， $n*m$ 数码问题的有解性判定，可以转化为归并排序求逆序对来解决。