# 线性时间的排序

## 排序的下界

首先引入决策树模型，决策树是一棵满二叉树，每个叶节点代表一种排序结果，而每个非叶节点代表一个比较操作，而决策树的高度就对应排序最坏的时间复杂度

而对于一个有 $n$ 个数的数组，其排序的结果有 $n!$ 种，也就是对应决策树叶节点有 $n!$ 个，而对于一棵高度为 $h$ 的满二叉树，其叶节点数为 $2^h$，所以有 $n! \leqslant 2^h$，所以 $h \geqslant \log (n!) = \Omega(n \lg n)$，也就是说任何比较排序的时间复杂度都不可能低于 $\Omega(n \lg n)$

为了能突破下界，可以考虑的方式有 **特殊情况**下不需要使用比较的排序 以及 不需要最优解的**近似**算法

## 计数排序

前提：数组中的元素都是在 $[0,k]$ 范围内的整数

思路：统计每个元素出现的次数，然后根据元素出现的次数，将元素放到正确的位置上

从后往前放的原因是为了保证排序的**稳定性**

时间复杂度为 $O(n+k)$，空间复杂度为 $O(n+k)$

计数排序适用于 $k$ 和 $n$ 相差不大的情况，不适用于稀疏的情况

## 基数排序

前提：数组中的元素都是 $d$ 位的整数，每一位的取值范围都是 $[0,k]$

思路：从低位到高位，对每一位进行计数排序 (稳定排序)

时间复杂度为 $O(d(n+k))$，空间复杂度为 $O(n+k)$，稳定

如果 $d$ 较大，但 $n$ 较小，可以考虑把 $r$ 位捆绑后排序，这样时间复杂度为 $O(\frac{d}{r}(n+k^r))$，因为 $r\leqslant d$
- 如果 $d<\lfloor\lg n\rfloor$，则可以取 $r=d$
- 如果 $d\geqslant \lfloor\lg n\rfloor$，则可以取 $r=\lfloor\lg n\rfloor$

## 桶排序

前提：数组中的元素是在区间 $[0,1)$ 间均匀分布的浮点数

思路：将区间 $[0,1)$ 分成 $n$ 个大小相同的子区间，然后将 $n$ 个元素分别放到对应的子区间中，然后对每个子区间进行插入排序，最后将所有子区间中的元素依次取出来

分析：$T(n)=\Theta(n)+\sum_{i=0}^{n-1}O(n_i^2)$

则期望时间复杂度为

$$ET(n)=E[\Theta(n)+\sum_{i=0}^{n-1}O(n_i^2)]=\Theta(n)+\sum_{i=0}^{n-1}O(n_i^2)$$

引入随机变量 $X_{ij}=I\{A[j]落入第i个桶\}$，则 $n_i=\sum_{j=1}^nX_{ij}$，$EX_{ij}^2=1^2\times 1/n+0^2\times(1-1/n)=1/n$，$EX_{ij}X_{ik}=1/n^2$

$$E[n_i^2]=E[(\sum_{j=1}^nX_{ij})^2]=\sum_{j=1}^nEX_{ij}^2+\sum_{j\neq k}EX_{ij}E_{ik}=2-\frac{1}{n}$$

因此有时间复杂度为 $\Theta(n)$