0x05 排序
在程序设计中，通常会使用到以下这些排序算法，这里把它们分为三类：
- 选择排序、插入排序、冒泡排序
- 堆排序、归并排序、快速排序
- 计数排序、基数排序、桶排序
前两类是基于比较多排序算法，
对 $n$ 个元素进行排序时，
若元素比较大小时间的复杂度为 $\mathcal{O}(1)$，
则第一类排序算法的时间复杂度位 $\mathcal{O}(n^2)$，
第二类排序算法的时间复杂度位 $\mathcal{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 (int i = 1; i <= n; i++) // 也可用 STL 中的 unique 函数
if (i == 1 || a[i] != a[i - 1])
b[++m] = a[i];
}
int query(int x) { // 查询 x 映射为哪个 1~m 之间的整数
return lower_bound(b + 1, b + m + 1, x) - b;
}
【例题】Cinema
中位数
在有序序列中，中位数具有一些很优美的特质，可以引出一系列与它相关的问题。
动态维护序列的中位数也非常值得探讨。
【例题】货仓选址
【例题】七夕祭
【例题】Running Median
第 $k$ 大数
给定 $n$ 个整数，如何求出第 $k$ 大的数？
我们当然可以直接对这 $n$ 个整数进行快速排序，然后输出从小到大排在第 $k$ 个的数，时间复杂度位 $\mathcal{O}(n \log{n})$。
实际上利用类似于快速排序的思想，只需要 $\mathcal{O}(n)$ 的时间即可求出第 $k$ 大数。
从大到小进行快速排序算法的思想是，在每一层递归中，随机选取一个数为基准，把比它大的数交换到 “左半段”，把其余的数和基准值自身一起作为 “右半段”，然后继续递归对左右两边分别进行排序，在平均情况下快速排序的复杂度为 $\mathcal{O}(n \log(n))$。
实际上在每次选取基准值后，我们可以统计出大于基准值的数的数量 $cnt$，
如果 $k \leq cnt$，我们就在左半段（比基准值大的数中）寻找第 $k$ 大数；
如果 $k > cnt$ 我们就在右半段（小于或等于基准值的数中——寻找第 $k - cnt$ 大数。
因此，寻第 $k$ 大数时，我们只需要进入左右两半二者之一继续递归，在平均情况下，复杂度为 $n + n / 2 + n / 4 \cdots + 1 = \mathcal{O}(n)$。
逆序对
对于一个序列 $a$，若 $i < j$ 且 $a[i] > a[j]$，则称 $a[i]$ 与 $a[j]$ 构成逆序对。
使用归并排序可以在 $\mathcal{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];
}
求逆序对的常用方法还有树状数组。