线性时间排序

排序算法的下界

决策树模型

在决策树中，每个内部结点都以 $i:\ j$ 标记，其中， $i$ 和 $j$ 满足 $1\le i,\ j\le n$ ， $n$ 是输入序列中的元素个数。每个叶结点上都标注一个序列。排序算法的执行对应于一条从树的根节点到叶结点的路径。对一个正确的比较排序算法来说， $n$ 个元素的 $n!$ 种可能的排列都应该出现在决策树的叶结点上。

最坏情况下界 在最坏情况下，任何比较排序算法都需要做 $\Omega(n\mathrm{lg}n)$ 次比较

考虑一颗高度为 $h$ 、具有 $l$ 个可达叶结点的决策树，所以有 $n!\ \le l$ 。由于在一棵高度为 $h$ 的二叉树中，叶结点的数目不多于 $2^h$ ，我们得到

n! \le l \le 2^h\\ \therefore h \ge \mathrm{lg}(n!)=\Omega(n\mathrm{lg}n)

计数排序

计数排序假设 $n$ 个输入元素中的每一个都是在 $0$ 到 $k$ 区间内的一个整数，其中 $k$ 为某个整数。当 $k=O(n)$ 时，排序的运行时间为 $\Theta(n)$ 。

计数排序的基本思想是：对每个输入元素 $x$ ，确定小于 $x$ 的元素个数。

在计数排序算法的代码中，假设输入是一个数组 $A[1..n]$ ， $A.length=n$ 。我们还需要两个数组： $B[1..n]$ 存放排序的输出， $C[0..k]$ 提供临时存储空间

COUNTING-SORT(A, B, k)
let C[0..k] be a new array
for i = 0 to k
	C[i] = 0
for j = 1 to A.length
	C[A[j]] = C[A[j]] + 1 //数组C存放A中元素的个数，C的下标就是A中元素的值，C的值就是A中元素的个数
for i = 1 to k
	C[i] = C[i] + C[i-1] //C数组的元素不断累加到C数组的后一个位置，最后一个位置的值是A中所有元素的数量，C[i]表示所有不大于i的元素的数量
for j = A.length downto 1
	B[C[A[j]]] = A[j] //A[j]是A数组中的某个值，C[A[j]]是A数组中不大于A[j]的元素个数，假如有3个，那么应该放在第4个位置，即B[3]
	C[A[j]] = C[A[j]] - 1 //C表中删除已放到B表的那个数

总代价为 $\Theta(k)+\Theta(n)+\Theta(k)+\Theta(n)=\Theta(k+n)$ ，当 $k=O(n)$ 时，运行时间为 $\Theta(n)$

计数排序的下界优于比较排序，它的代码中完全没有输入元素之间的比较操作。相反，使用输入元素的实际值来确定其在数组中的位置。

计数排序是稳定的：具有相同值的元素在输出数组中的相对次序与他们在输入数组中的相对次序相同。

基数排序

一张卡片有80列，在每一列上机器可以选择在12个位置中的任一处穿孔。通过机械操作，我们可以对排序机编程来检查每个卡片中的给定列，然后根据穿孔的位置将它们分别放入12个容器中，操作员可以逐个容器收集卡片，其中第一个位置穿孔的卡片在最上面。

对十进制数字来说，每列10个位置，一个d位数将占用d列，例如114514

-	-	-	-	-	-
O	O	-	-	O	-
-	-	-	-	-	-
-	-	-	-	-	-
-	-	O	-	-	O
-	-	-	O	-	-
-	-	-	-	-	-
-	-	-	-	-	-
-	-	-	-	-	-
-	-	-	-	-	-

基数排序先按最低有效位进行排序，对每个卡片只按最低位依次放入对应序号的容器中，再按容器顺序取出卡片合并成一叠，这时候按照次低位放入容器，以此类推。

1
2
3

RADIX-SORT(A, d)//A数组中有n个d位数
for i = 1 to d
	use a stable sort to sort array A on digit i

给定 $n$ 个 $d$ 位数，其中每一个数位有 $k$ 个可能的取值。如果基数排序使用的稳定排序方法耗时 $\Theta(n+k)$ ，那么它就可以在 $\Theta(d(n+k))$ 时间内将这些数排好序，当 $d$ 为常数且 $k=O(n)$ 时，基数排序具有线性的时间代价

我们也可以认为划分某一些位数组合成一个数，从而改变 $d$ 的值

桶排序

桶排序假设输入数据服从均匀分布，平均情况下的时间代价为 $O(n)$ 。

桶排序将 $[0,\ 1)$ 区间划分为 $n$ 个大小相同的子区间，或称为桶。然后将 $n$ 个输入数分别放到各个桶中。为了得到输出结果，先对每个桶中的数进行排序，然后遍历每个桶，按照次序把各个桶中的元素列出来即可。

假设输入是包含 $n$ 个元素的数组 $A$ ，且每个元素满足在 $[0,\ 1)$ 之间，临时数组 $B$ 用来存放链表(桶)

BUCKET-SORT(A)
n = A.length
let B[0..n-1] be a new array
for i = 0 to n-1
	make B[i] an empty list
for i = 1 to n
	insert A[i] into list B[nA[i]]
for i = 0 to n-1
	sort list B[i] with insertion sort
concatenate the lists B[0], B[1],...,B[n-1] together in order

下面分析桶排序的时间代价，考虑到插入排序时间代价为平方阶

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

对所有 $i=0,\ 1,\ ...,\ n-1$ 和 $j=1,\ 2,\ ...,\ n$

X_{ij}=I\{A[j]落入桶i\}

因此，

n_i=\sum_{j=1}^nX_{ij}

则

E[n_i^2]=E[(\sum_{j=1}^nX_{ij})^2]\\ =E[\sum_{j=1}^n\sum_{k=1}^nX_{ij}X_{ik}]\\ =E[\sum_{j=1}^nX_{ij}^2+\sum_{1\le j\le n}\sum_{1\le k \le n,k\ne j}X_{ij}X_{ik}]\\ =\sum_{j=1}^nE[X_{ij}^2]+\sum_{1\le j\le n}\sum_{1\le k \le n,k\ne j}E[X_{ij}X_{ik}]

考虑到 $P\{X_{ij}=1\}=1/n$

E[X_{ij}^2]=1^2\cdot\frac{1}{n}+0^2\cdot(1-\frac{1}{n})=\frac{1}{n}\\ \because k \ne j时，X_{ij}和X_{ik}是独立的\\ \therefore E[X_{ij}X_{ik}]=E[X_{ij}]E[X_{ik}]=\frac{1}{n}\cdot\frac{1}{n}\\ \therefore E[n_i^2]=\sum_{j=1}^n\frac{1}{n}+\sum_{1\le j\le n}\sum_{1\le k \le n,k\ne j}\frac{1}{n^2}=2-\frac{1}{n}

因此，桶排序的期望运行时间为

\Theta(n)+n\cdot O(2-\frac{1}{n})=\Theta(n)