前言

学习了一个学习的算法设计与分析，在这里做一个期末复习专题来回顾一下后半学期的知识。

PS：本篇题目与分篇中大部分不太相同，可能是其他的例子（也可能不是），为了更好的理解这些问题。

PS：这里不包括分治法及其之前的内容，具体请见各自章节。

算法设计与分析

这一篇复习涉及到的内容：

• 散列表——开放定址法（双散列）
• 动态规划——最优二叉搜索树
• 贪心算法——哈夫曼编码
• 基本图论——BFS、DFS
• 单源最短路——Bellman-Ford 算法, Dijkstra算法
• 堆排序
• 线性时间排序

---

散列表——开放定址法（双散列）

本章原文：

【算法设计与分析】散列表

我们一般使用双散列比较多，下面是一个使用双散列的例子：

Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length m = 11 using open addressing.
Illustrate the result of inserting these keys using double hashing with h1(k) = k mod m and h2(k) = 1 + (k mod (m – 1)).

我们整合一下上面的两个函数，可以得到函数h(k,i)，k表示关键字，i从0开始，表示初始位置的基础上进行偏移的度：
h(k, i) = (h1(k) + i*h2(k)) mod m
= (k mod m + i(1 + (k mod (m – 1)))) mod m

我们的操作如下：

1. 对于键值对10：h1(10) = 10 mod 11 = 1，插入键值对10到哈希表的第10个位置。
2. 接下来是键值对22：h1(22) = 22 mod 11 = 0，插入键值对22到哈希表的第0个位置。
3. 现在是键值对31：h1(31) = 31 mod 11 = 9，插入键值对31到哈希表的第9个位置。
4. 接下来是键值对4：h1(4) = 4 mod 11 = 4，插入键值对4到哈希表的第4个位置。
5. 现在是键值对15：h1(15) = 15 mod 11 = 4，4这个位置冲突了，继续计算h2(15) = 1 + (15 mod (11 – 1)) = 1 + 5 = 6，(4 + 6) mod 11= 10这个位置还是冲突，继续计算(4 + 2*6) mod 11 = 16 mod 11 = 5，插入键值对15到哈希表的第5个位置。
6. 接下来是键值对28：h1(28) = 28 mod 11 = 6，插入键值对28到哈希表的第6个位置。
7. 现在是键值对17：h1(17) = 17 mod 11 = 6，这个位置冲突了，计算h2(17) = 1 + (17 mod (11 – 1)) = 1 + 7 = 8，(6 + 8) mod 11 = 3，插入键值对17到哈希表的第3个位置。
8. 接下来是键值对88：h1(88) = 88 mod 11 = 0，位置冲突继续计算，h2(88) = 1 + (88 mod (11 – 1)) = 1 + 8 = 9，(0+9) mod 11 = 9冲突，继续计算(0+2*9) mod 11 = 7，插入键值对88到哈希表的第7个位置。
9. 最后是键值对59：h1(59) = 59 mod 11 = 4，位置冲突继续计算，h2(59) = 1 + (59 mod (11 – 1)) = 1 + 9 = 10，(4+10) mod 11 = 3冲突，(4+2*10) mod 11 = 2，插入键值对59到哈希表的第2个位置。

最后可以得到如下表格：

---

动态规划——最优二叉搜索树

本章原文：

【算法设计与分析】动态编程

在上述章节中，对过程描述得非常详细，原理部分将不再展示，下面将会修改一些数据，用另外的例子来回顾这章内容。同理，我们先列出表定义：

以及新例子的概率表：

我们先从w表开始，它的公式为：

填表有如下规律：

• 首先先填对角线，填入q_i的所有内容。
• 然后再填已填写位置右侧的一格（例如已填写w[1,0], 那么接下来就填w[1,1]），它的内容根据公式等于左侧单元格内容 + 当前列号(j)对应的p_j和q_j的概率和。
• 这是一个斜向右填表的过程，如果已经到达右边的边上，则不用填。每次要填写的数据都少一个（即第一次填6个，第二次就填5个，因为最后那个已经到达边上）。

接下来是e表和root表，e表的公式为：

填表有如下规律：

• 首先也是对角线的值为q_i；
• 之后的值中，r的取值有j-i种，需要每个讨论j-i次。
• 每次讨论等价于对位相加。例如第1次讨论则是e表中这一行的第1个数 + e表中这一列的第1个数 + w表中该位置的值。即对于e[i,j]的第k(k∈[i,j])次讨论，为该行（第i行）的第k个数 + 该列（第j列）的第k个数 + w[i,j]。
• 对于讨论中相同的值，选择讨论次数k最小的，因为替换最小值时比较为<而不是≤。
• 这个过程也是斜向右填表，越往后的讨论次数越多。
• 对于root表，它的行和列为1-n，也是从对角线开始填。右上角为整个树的根。

root表：

i\j	1	2	3	4	5	6	7
1	1	2	2	2	3	3	5
2		2	3	3	3	5	5
3			3	3	4	5	5
4				4	5	5	6
5					5	6	6
6						6	7
7							7

最后根据这个表，生成一个树如图：

---

贪心算法——哈夫曼编码

本章原文：

【算法设计与分析】贪心算法

哈夫曼编码的贪心设计就非常明显了，只需要使用优先队列去存，每次都选择最小的两个合并，直到全部插入树中即可，例如：

以下字符频率基于斐波那契数列前8个数字的字符集的哈夫曼编码是怎样的?
a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21

下面使用z(a,b)表示频数为z的节点左边的是频数a或字符a，右边的是频数b或字符b。

1. 把它们按照频数加入优先队列Q中，顺序刚好为：a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21
2. 取出前两个，合并插入到优先队列中得到：c:2 2(a,b) d:3 e:5 f:8 g:13 h:21
3. 依次类推继续合并插入得：d:3 4( c,2(a,b) ) e:5 f:8 g:13 h:21
4. e:5 7( d,4( c,2(a,b) ) ) f:8 g:13 h:21
5. f:8 12( e, 7( d,4( c,2(a,b) ) ) ) g:13 h:21
6. g:13 20( f,12( e, 7( d,4( c,2(a,b) ) ) ) ) h:21
7. h:21 33( g,20( f,12( e, 7( d,4( c,2(a,b) ) ) ) )
8. 54( h,33( g,20( f,12( e, 7( d,4( c,2(a,b) ) ) ) ) )

最终得到这样的一棵树，图(a)为该题答案，图(b)为前n为推广：

---

基本图论

本篇原文：

【算法设计与分析】基础图论算法

BFS

BFS的搜索过程是一层一层向外的，就犹如水波(wave)一样。简单来说，对于BFS的过程如下：

1. 从s开始，一层一层地发现顶点。
2. 首先访问距离s只有1条边的所有顶点(s的下一层)。
3. 从那些顶点开始，访问距离下一层的所有顶点，以此类推。
4. 直到它发现了从s出发可到达的每个顶点。

用下列的值表示：

• v.d 表示从s到v的距离。
• v.π 表示v的在广度优先树中的前驱，若v为源点或者未被发现，故v没有前驱，初始设v.π = NIL。

我们通过一个例子来进一步掌握：

对于如下的图，设从s出发，求以字典序的BFS中，每个顶点的d值表、π值表和队列出队顺序Q。

1. 遍历与s相邻的节点，并把s出队，那些节点按照字典序入队，给它们的d赋值1，π赋值为s。此时队列S: r, u, v；
2. 接下来r出队，并把其相连的t和w入队，并给它们d = 2，π = r，S: u, v, t, w；
3. u出队，并把其相连的且没有被访问过的y入队，并给它d = 2，π = u，S: v, t, w, y；
4. v出队，与它相邻的均以入队，S: t, w, y；
5. t出队，与它相邻的均以入队或已经出队，S: w, y；
6. w出队，并把其相连的且没有被访问过的x和z入队，并给它们d = 3，π = w，S: y, x, z；
7. y出队，与它相邻的均以入队或已经出队，S: x, z；
8. x出队，与它相邻的均以入队或已经出队，S: z；
9. z出队，与它相邻的均以入队或已经出队，S: Empty；

把这个过程整合成表格得：

	r	s	t	u	v	w	x	y	z
v.d	1	0	2	1	1	2	3	2	3
v.π	s	NIL	r	s	s	r	w	u	w

Q: s, r, u, v, t, w, y, x, z

---

DFS

DFS则是先探索一条道路到头，再回溯到分叉口进行其他探索。

与BFS不同的是，DFS必须访问所有的顶点，所以可能深度优先搜索有多个源点。还有广度优先搜索的前驱子图是一棵树，但是深度优先搜索的前驱子图可能包含若干棵树，这是由于搜索可能从多个源点进行。

除了之前BFS的d外，深度优先搜索还给每个顶点加时间戳(timepstamp)。

每一个顶点v有两个时间戳：第一个时间戳v.d记录了v第一次被发现的时间(discovery time)，第二个时间戳v.f 记录了v被搜索结束的时间(finish time)。

例如下面的这个例子：

如图，以字典序进行DFS搜索，输出一个d表和f表。

1. 以字典序的DFS，那么我们应该以q开始，因为它字典序最小。
2. 按照字典序，先走s这条路径，一路走到：q->s->v->w，此时走到头了，一直回溯到分叉口q处。此时有：q: 1/? s:2/7 v:3/6 w:4/5. q的f为?是因为还有一个箭头指向它，可能之后还有访问到，f记录的是最后访问的时间戳。
3. 接着沿着t这条路径走，根据字典序选择x这边：q->t->x->z，走到头了回溯到分叉口t，接着往y处走：t->y->q，整条路径为：q->t->x->z->z->x->t->y->y->t->q，于是有：q: 1/16 t: 8/15 x:9/12 z:10/11 y:13/14 
4. 左半部分遍历完了，接下来根据字典序，找到没有被遍历的最小字母r，走u这条路径，有：r:17/20 u:18/19

输出为表格得：

这整个过程的遍历图为：

---

单源最短路

本篇原文：

【算法设计与分析】单源最短路算法

Bellman-Ford 算法

Bellman-Ford算法解决的是一般情况下单源最短路径问题，边的权重可以为负值，给定源点为s的有向带权图 G =(V, E)和权重函数 w: E->R，Bellman-Ford算法返回一个布尔值，该布尔值表明是否存在一个从源点可达的负权重的环路。若存在这样一个环路(有负权重的环路)，则算法提示不存在解决方案(False)。若不存在这样一个环路，则算法给出最短路径和它们的权重(True)。

算法的思路为：

1. 初始化将所有顶点的d值设置为∞，π值设置为NIL。设置源点d = 0.
2. 进行n - 1次遍历，每次遍历对所有边进行松弛操作，满足则将权值更新。
3. 遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路(FALSE)否则为TRUE。

例如：如果设s为源点，按照如下顺序(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)松弛边的话，如下图，找出每个节点的d值(最短路长)和π值(前驱节点)的表格。

1. 首先，通过INITIALIZE-SINGLE-SOURCE操作，将所有顶点的d值设置为∞，π值设置为NIL。设置源点s.d = 0.
2. 第一次循环：从s出发，按照顺序遍历这些节点，此时根据(s, t), (s, y)，我们可以把t和y的值设置：t.d = 6, t.π = s; y.d = 7, y.π = s。
3. 第二次循环：根据顺序有(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)，通过松弛这些边得到：x.d = 11, x.π = t; z.d = 2, z.π = t; x.d = 4, x.π = y。
4. 第三次循环中，在松弛边(x, t)时，t.d = 2, t.π = x。
5. 在算法的最后一个步骤中，再进行一次遍历，在松弛边(t, z)时，z.d = -2, z.π = t；在松弛边(z, x)时，x.d = 2, z.π = z。
6. 这个结果导致某些节点有更短的路径，则存在负权边，返回FALSE，验证：因为在松弛边(t, z)时，z.d = -2, z.π = t；在松弛边(z, x)时，x.d = 2, z.π = z。此时负权环为(t, z), (z, x), (x, t)边组成。

整合成表得：

d值表：

s	t	x	y	z
0	∞	∞	∞	∞
0	6	∞	7	∞
0	6	4	7	2
0	2	4	7	2
0	2	2	7	-2

π表为：

s	t	x	y	z
NIL	NIL	NIL	NIL	NIL
NIL	s	NIL	s	NIL
NIL	s	y	s	t
NIL	x	y	s	t
NIL	x	z	s	t

 

---

Dijkstra算法

Dijkstra的算法解决了加权有向图上的单源最短路径问题，但它要求所有边的权重是非负的。

Dijkstra算法维持一个顶点集合 S，表示从s可达的最终最短距离已经确定的顶点的集合。Dijkstra算法不断从 V -S 中选择具有最小路径估计的顶点 u，然后将u加入 S，并松驰所有从u发出的边。即节点u出队时进入S中。
过程 Dijkstra 使用以顶点的 d 值为关键字的优先队列Q。

下面是一个例子：

如下图，若我们以z为源点，找到所有顶点在算法过程中的d值和π值，以及集合S表示最短路径。

1. 首先，通过INITIALIZE-SINGLE-SOURCE操作，将所有顶点的d值设置为∞，π值设置为NIL，S和Q为Ø。设置源点z.d = 0，z入队.
2. 接下来，z出队，s和x进入优先队列Q，更新s和x的值：s.d = 3, s.π = z；x.d = 7，x.π = z；此时最短路集合S = z。
3. s出队，t和y进入优先队列Q，更新值为：t.d = 6, t.π = s；y.d = 8, y.π = s，此时最短路集合S = z, s。
4. t出队（它的权比x小），无事发生，此时最短路集合S = z, s, t。
5. x出队，无事发生，此时最短路集合S = z, s, t, x；
6. y出队，无事发生，此时最短路集合S = z, s, t, x, y；

d值表：

s	t	x	y	z
∞	∞	∞	∞	0
3	∞	7	∞	0
3	6	7	8	0
3	6	7	8	0
3	6	7	8	0

π值表：

s	t	x	y	z
NIL	NIL	NIL	NIL	NIL
z	NIL	z	NIL	NIL
z	s	z	s	NIL
z	s	z	s	NIL
z	s	z	s	NIL

S = z, s, t, x, y

---

堆排序

本篇原文：

【算法设计与分析】堆排序分析

这一节又分为分析和代码部分，其中比较重要的是如何维护堆和建堆。下面的证明可能与之前原文有所不同，选择好理解的就行。

分析

证明左子树最大规模为2n/3

由于堆是对应一棵完全二叉树，设它有n个结点根结点。根的左子树结点数≥根结点的右子树结点数。

对于一个完全二叉树，它的最后一层可能不是完全填满的。为了估计最大规模，假设我们假设左子堆是一个高度为h的满二叉树，右子堆是一个高度为h-1的满二叉树。

那么左子树的结点数nl = ∑i∈[0,h] 2i = 2(h+1) - 1；右子树的结点数nr = ∑i∈[0,h-1] 2i = 2h - 1

总结点数n = nl + nr + 1 = 2(h+1) - 1 + 2h - 1 + 1 = 3*2h - 1

于是左子树结点数/总结点数 = 2(h+1) - 1 / 3*2h - 1 = 2*2h - 1 / 3*2h - 1 < 2*2h / 3*2h = 2/3 故左子树最大规模为2n/3。

分析维护堆

维护堆是一个向下调整（Percolate Down）的过程，如果为大根堆，则判断当前根结点是否满足大于它的左右结点，如不满足，则替换为左右结点中最大的，接着递归以被替换位置为根向下调整。

它的伪代码为：

MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] > A[i]
        largest = l
    else largest = i
    if r ≤ A.heap-size and A[r] > A[largest]
        largest = r
    if largest ≠ i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

分析它非常简单，我们之前已经知道了子树最大规模为2n/3，故递归式为：T(n) = T(2n/3) + Θ(1)；

根据Master Theorem Case 2，n^{log_2/3 1} = 1 ∈ Θ(1)，故T(n) = Θ(lgn)

证明：对一个大小为n的堆，MAX-HEAPIFY的最坏情况运行时间为Ω(lgn)

MAX-HEAPIFY的最坏情况下（是一个小根堆），每个根都需要运行一次MAX-HEAPIFY，此时一条路径上最长的为 h = ⌊lgn⌋，故最坏的运行时间为Ω(lgn)。

证明叶结点下标

证明: 当用数组表示存储n个元素的堆时，叶结点的下标分别为⌊n/2⌋ +1,⌊n/2⌋ +2, ..., n。

这个很容易证明，我们想最后一个结点为n，它的父母结点p为⌊n/2⌋。此时有三种情况：

1. 当父母结点p的左孩子为n的时候，且p不在这一层的末尾，那么p+1开始的结点到n都是叶子节点。例如下图的堆：最后一位结点n的下标为8，值为1，它的父母结点的下标为⌊n/2⌋ = 4，那么从⌊n/2⌋+1到n的结点(4, 3, 2, 1)它们都是叶子节点。

           8
         /   \
        7     6
       / \   / \
      5   4 3   2
     /
    1

2. 当父母结点p的右孩子为n的时候，且p不在这一层的末尾，那么p+1开始的结点到n都是叶子节点。同理为右结点时，p的下一位一定也是叶子结点。例如：最后一位结点n的下标为9，值为2，它的父母结点的下标为⌊n/2⌋ = 4，那么从⌊n/2⌋+1到n的结点(4, 3, 2, 1, 2)它们都是叶子节点。

           8
         /   \
        7     6
       / \   / \
      5   4 3   2
     / \
    1   2

3. 当父母结点p的右孩子为n的时候，且p在这一层的末尾，那么p+1开始的结点到n都是叶子节点。此时这种情况下像之前所知的无论最后一位是左右都无所谓，父母结点的下一个就在最后一位的这一层，它们都是叶子结点。例如：最后一位结点n的下标为7，值为2，它的父母结点的下标为⌊n/2⌋ = 3，那么从⌊n/2⌋+1到n的结点(5, 4, 3, 2)它们都在最后一层，是叶子节点。

           8
         /   \
        7     6
       / \   / \
      5   4 3   2

上述为理解证明，但实际上证明可以使用反证法来证明：

假设 ⌊n/2⌋+1不位于最后一层，那么它一定有左孩子，其左孩子结点下标小于等于n。

我们证明它的左孩子：LEFT(⌊n/2⌋+1) = 2(⌊n/2⌋+1) 因为(n/2-1)≤⌊n/2⌋≤n/2，那么2(⌊n/2⌋+1)≥2(n/2-1+1) = n，此时它的左孩子一定大于等于n，假设不成立得证。

证明在高h的层上至多的结点数

首先，我们先回顾：从根到节点的简单路径的长度是树中节点的深度。树的高度是从节点到叶子的最长下行路径上的边数，树的高度是它的根的高度。这意味着，高度从下往上依次是0~H，而深度则是从上往下依次是0~H。

有了上一个证明，我们知道n元堆的叶结点的下标分别为⌊n/2⌋ +1,⌊n/2⌋ +2, ..., n。

那么叶子结点的总数有：n - (⌊n/2⌋ +1) + 1 ≥ ⌈n - n/2⌉ = ⌈n/2⌉

设高度为h的层有n_h个结点，那么高度为0的层，它至多有⌈n/2⌉个叶子结点，因为当叶子结点全都在最后一层时成立。

那么使用数学归纳法：在高度为h的层有n_h个结点，n_h ≤ ⌈n/2^(h+1)⌉，

则在高度为h+1的层的结点数为n_h+1 ≤ ⌈n_h/2⌉ = ⌈n/2^(h+1) /2⌉ = ⌈n/2^(h+1) /2⌉ = ⌈n/2^{(h+1 + 1)}⌉得证。

故在高h的层上至多的结点数为⌈n/2^(h+1)⌉。

建堆分析

我们知道对于一颗完全二叉树，根的左子树结点数≥根结点的右子树结点数。那么当它满的时候，这棵树的高度为⌊lgn⌋。

下面是建堆的代码：

BUILD-MAX-HEAP(A, n)
    A.heap-size = n
    for i = floor(n/2) down to 1
        MAX-HEAPIFY(A, i)

这个算法是从最后一个结点的父母结点开始，不断向上调整的过程。在每个MAX-HEAPIFY(A, i)中，它的时间复杂度看作是节点i到叶子节点的路径长度，这个路径长度等于这个节点的高度。因此，对于一个高度为h的节点，它的时间复杂度为O(h)。

在一个高度为H = ⌊lgn⌋的完全二叉树中，高度为h的节点有2^(H-h) = 2^{(⌊lgn⌋-h)} = 2^⌊lgn⌋/2^h个。根据之前的证明可以得到 2^⌊lgn⌋/2^h ≤ ⌈n/2^(h+1)⌉

设c为渐近符号中隐含的常数，故整个的时间复杂度为：

∑_{(h=0 to H-1)} 2^(H-h) * O(h) * c

≤ ∑_{(h=0 to H-1)} ⌈n/2^(h+1)⌉ * h * c

= cn ∑_{(h=0 to ⌊lgn⌋-1)} h/2^(h+1)
≤ cn ∑_{(h=0 to ∞)} h/2^(h+1)

这里对于几何级数，当0<x<1时，∑_{(n=0 to ∞)} xⁿ = 1 / (1 - x)。

对这个公式两边同时求导(对x)，得到∑_{(n=0 to ∞)} n * x^(n-1) = 1 / (1 - x)²，我们带入x = 1/2，得到∑_{(n=0 to ∞)} n * (1/2)^(n-1) = 1 / (1 - 1/2)² = 4。

将两边同时乘以(1/2)²，得到∑_{(n=0 to ∞)} n * (1/2)ⁿ⁺¹ = 1。

回到原题中，这里的∑_{(h=0 to ∞)} h/2^(h+1) = h * (1/2)^h+1 = 1. 故有：

cn ∑_{(h=0 to ∞)} h/2^(h+1)

=cn * 1

=cn

=O(n)

于是乎建堆的过程，时间复杂度为O(n)。

分析堆排序

HEAPSORT(A, n)
    BUILD-MAX-HEAP(A, n)
    for i = n downto 2
        swap(A[1], A[i])
        A.heap-size = A.heap-size - 1
        MAX-HEAPIFY(A, 1)

对于堆排序，它的过程就非常简单了，因为有n-1次循环，每次MAX-HEAPIFY(A, 1)的时间复杂度为O(lgn)，堆排序的时间复杂度为O(n lgn)

---

代码

编写MIN-HEAPIFY(A,i)

维护堆是一个向下调整（Percolate Down）的过程，根据大根堆的思路，很容易知道小根堆的思路为找到i结点的左右结点，判断i结点是否为最小的，不是则替换，并递归被替换的位置。

于是它的伪代码：

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r ≤ A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest != i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)

使用循环重写MAX-HEAPIFY

我们可以用循环来替换递归来提高效率。当最后的largest == i时，我们结束循环。 于是就有：

MAX-HEAPIFY(A, i)
    while true
        l = LEFT(i)
        r = RIGHT(i)
        if l ≤ A.heap-size and A[l] > A[i]
            largest = l
        else largest = i
        if r ≤ A.heap-size and A[r] > A[largest]
            largest = r
        if largest == i
            return
        exchange A[i] with A[largest]
        i = largest

---

线性时间排序

本篇原文：

【算法设计与分析】线性时间排序

分析

证明比较排序的下界

对于一棵每个排列都是一个可达的叶结点的决策树来说，树的高度完全可以被确定。考虑一棵高度为h的决策树，它对应一个对n个元素所做的比较排序。

对于n个变量的问题，这n个变量有n!种可能的顺序，它在决策树中就有n!个叶结点。根据图中情况可以知道，若为满二叉树，在h层有2^h个叶子结点，明显n! <= 2^h。

两边取对数得：h >= lg(n!)

根据Sterling 近似公式，有n! ≈ √(2πn)(n/e)n => n! > (n/e)n带入可得，h ≥ lg(n/e)n = n lg(n/e) = n lg n – n lg e = Ω(n lg n)

分析桶排序

桶排序的步骤为：

1. 根据A数组新建B链表数组，并初始化为0。
2. 将A数组中的元素依次按照一定的规则插入到桶中。（有点像散列表）。
3. 对每个桶内部进行插入排序，当插入排序规模很小的时候，趋向于Θ(n)。
4. 按顺序输出每个桶（桶设置时是有序的）。

它的伪代码：

BUCKET-SORT(A, n)
    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[⌊n · A[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
    return the concatenated lists

在最坏的情况下(所有的数据都插到同一个桶中)，我们发现除了插入排序外，其他的均为Θ(n)。因为插入排序的时间代价为平方阶的，那么整体的桶排序时间代价为：T(n) = Θ(n) + ∑(0,n-1)O(n2)

我们计算平均的运行时间，对这个式子取数学期望(mean)：

E( T(n) )= Θ(n) + E (∑(0,n-1)O(ni2) )
= Θ(n) + ∑(0,n-1)O( E(ni2) )

一共有n个桶，这个数据落入这个桶的概率为1/n，数据落入桶这个过程它满足二项分布ni ~ B(n,1/n)

E( T(n) )= Θ(n) + ∑(0,n-1)O( E(ni2) )
= Θ(n) + ∑(0,n-1)O( 2 - 1/n )
= Θ(n) + O(n)
= Θ(n)

因为在二项分布中：

• E(x) = np = 1;
• Var(x) = np(1-p) = 1 - 1/n;
• E(x2) = Var(x) + E2(x) = np(1-p) + (np)2 = 1 - 1/n + 1 = 2 - 1/n;

故平均情况下为Θ(n) 但最坏的情况为Θ(n2)，因为插入排序最差情况为Θ(n2)

---

代码

修改计数排序

设由n个元素组成的输入序列每个元素都是区间[0: k]内的一个整数，且这些元素没有卫星数据，修改COUNTING-SORT，只用数组 A和C，将输出序列放在A中。

这样输入序列所有元素只能从 C 中复制，修改后COUNTING-SORT的伪代码如下：

COUNTING-SORT(A, n, k)
    let C[0:k] be new arrays
    for i = 0 to k
        C[i] = 0
    for j = 1 to n
        C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i.
    p = 1
    for i = 0 to k
        while C[i] > 0
            A[p] = i
            p = p + 1
            C[i] = C[i] - 1

基于CDF的桶排序

设X为一个随机变量，设它的累计分布函数(CDF)为F(x) = P(X≤x)，设X₁,X₂,... , X_n服从F(x)，且在 O(1) 时间内可以计算得到(若给定 y 和 F(x)=y，能够在 O(1) 时间内计算出x )，设计一个算法，能在平均情况为线性时间内完成排序。

这样的算法我们可以使用桶排序，设置F(x) = i/n，有n个桶，它们就满足二项分布了，这个就和桶排序基本一致，于是我们的伪代码可以写为：

BUCKET-SORT(X, n)
    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
        if x_{i-1} ≤ X_i and X_i < x_i
        insert X_i into list B[i-1]
    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
    return the concatenated lists