[TOC]
应用
一、排序
本章介绍了插入排序和快速排序两种排序算法的优化。
1.1 插入排序
插入排序的原理是一个递推的过程，是在数组一端形成有序区，然后将无序区的元素逐一插入到有序区，有序区逐渐向无序区方向扩张的过程。例如数组{3, 1, 4, 2}的插入排序过程如下：
3 | 1 4 2
1 3 | 4 2
1 3 4 | 2
1 2 3 4 |
可以使用基于交换的方式实现，若有序区中最靠近目标元素的元素 比目标元素大 则交换目标元素和该元素，此时目标元素进入有序区，继续与前一个元素进行比较：
void swap(int* x, int m, int n){
int temp = x[m];
x[m] = x[n];
x[n] = temp;
}
void isort(int* x, int length){
for(int i = 0; i < length; i++){
for(int j = i; j > 0 && x[j-1] > x[j]; j--){
swap(x, j-1, j);
}
}
}
以上插入排序程序存在一个问题，调用swap函数也存在额外的花销。可以将swap函数拆解为代码或定义为宏，程序运行速度会有一定提升
void isort1(int* x, int length){
for(int i = 0; i < length; i++){
for(int j = i; j > 0 && x[j-1] > x[j]; j--){
// 用代码“取缔” swap 函数
int temp = x[j];
x[j] = x[j-1];
x[j-1] = temp;
}
}
}
另外，无差别使用交换会造成许多冗余的赋值过程。以下插入排序程序，将交换操作替换为花销更低的平移操作，将有序区中比目标元素更大的元素整体向右平移，从而规避了这个问题：
void isort2(int* x, int length){
for(int i = 0; i < length; i++){
int t = x[i];
for(int j = i; j > 0 && x[j-1] > t; j--){
x[j] = x[j-1];
}
x[j] = t;
}
}
1.2 快速排序
快速排序是基于分治的思想，基于递归的时间复杂度为 NLogN 的排序算法。其原理是首先确立一个元素的最终位置，从而将序列按该元素划分为两个子序列，若升序排序则左子序列所有元素值的值均小于该元素，右子序列的所有元素值均大于该元素值，然后递归地对左子序列和右子序列进行快速排序。
需要确定最终位置的元素称为轴元素，刚开始可以把轴元素选择策略定简单点，就直接用最左侧元素。至此，快速排序实现的关键是：如何将比轴元素小的元素交换到轴元素左侧，且将大于轴元素的元素交换到轴元素右侧。第一种方法是基于递推，实现过程如下，原理标注在注释中。
void qsort(int* x, int l, int u){
if(l >= u)
return;
// 1. 选定最左侧元素为轴元素，m 用于记录是轴元素在已扫描序列中的最终位置，从轴元素开始
// 扫描序列，初始已扫描序列为 x[l]，所以 m 的初始值是 l;
int m = l;
// 2. 继续从轴元素的下一个元素开始循环扫描;
for(int i = l+1; i <= u; i++){
// 2.1 若扫描元素比轴元素小，则递增 m，将扫描元素 x[i] 与 x[m] 交换（保证 x[l+1...m] < x[l]）
if(x[i] < x[l]){
swap(x, i, ++m);
}
// 2.2 若扫描元素大于等于轴元素，则直接扫描下一个元素（保证 x[m+1...u] >= x[l]）
// 2.3 因此在循环过程中始终能保证该不变式成立：x[l+1...m] < x[l] && x[m+1...u] >= x[l]
}
// 3. 循环结束后，m 就是轴元素的最终位置，而且 x[m] < x[l]，所以直接交换 x[i] 与 x[m] 元素即可
swap(x, l, m);
qsort(x, l, m-1);
qsort(x, m+1, u);
}
上面的算法存在一个问题：对于所有元素相同的长度为 n 的数组，由于每次探测的轴元素最终位置都在数组末端，因此算法的递归层数由理想的 log2n 退化为 n，此时算法运行时间级数就会退化为 n2。
可以使用双向扫描的方式，解决这个问题。仍然选择第一个元素作为轴，在计算轴元素最终位置的循环内部再嵌套两个循环，分别用于从首端向末端探测第一个大于等于轴元素的元素 x[i]，从末端向首端探测第一个小于等于轴元素的元素 x[j]：
- 当 i > j 时，说明 x[j+1...n-1] >= x[0] && x[0...i-1] <= x[0]，而 x[j] 本身比轴元素小，因此 x[j] 可以作为数组的分割点，此时跳出循环并交换轴元素 x[0] 和 x[j] 即可；
- 当 i<= j 时，尚未探测到数组的分割点，此时 x[i] 需要移到分割点右端而 x[j] 需要移到分割点左端，因此只要将两者交换即可，然后递增 i、j 并进入下一次循环迭代；
考虑双向扫描方式在数组元素相同的极端情况下的执行过程。外层循环第一次迭代探测结果必然是 i = 0 j = n-1 为数组两端，对非空数组必然有 i <= j，因此递增 i、j 并进入下一次循环迭代。以此类推 i、j 会在此过程中不断向数组中点收敛，最终到达数组中点。因此对所有元素相同的情况算法的递归层数仍然是 log2n。算法的实现如下：
void qsort2(int* x, int l, int u){
if(l >= u)
return;
// 1. 选定最左端元素为轴元素，用变量 i、j 记录两个方向扫描的当前位置
int t = x[l], i = l, j = u + 1;
for(;;){
// 2. 向右找到第一个大于等于轴元素的元素
do { i++; } while(i <= u && x[i] < t);
// 3. 向左找到第一个小于等于轴元素的元素
do { j--; } while(x[j] > t);
// 注意：上面这句代码非常细节，本来按道理应该需要 j >= l 限制条件的，但由于 x[l] 为轴元素，
// 因此循环探测到达轴元素时 x[j] > t 就一定不成立，所以 j >= l 这个判断直接去掉
// 4. 如果左侧已扫描序列和右侧已扫描序列完成交叉，则 j 可以直接作为轴元素的最终位置，
// 因为满足不变式：x[j...u] >= x[l] && x[l...j] <= x[l]
if(i > j)
break;
// 5. 如果左侧已扫描序列和右侧已扫描序列未交叉，则继续下一个循环（递增 i、j 的操作在上面
// 的 do-while 语句中完成）
swap(x, i, j);
}
// 6. 将轴元素交换到最终位置
swap(x, l, j);
// 7. 递归
qsort2(x, l, j-1);
qsort2(x, j+1, u);
}
到目前为止的排序算法都是围绕第一个元素作为轴元素来进行的，但是这样会带来一个问题：对于已排序的数组，算法的运行时间级数会退化到 n2。原因跟之前的类似，还是因为每次探测轴元素最终位置都是数组的首端或末端导致递归层数由 log2n 退化为 n。一种比较简单的解决方式是，随机选择轴元素，然后交换到数组首元素，再使用上面的算法进行排序。
void qsort2(int* x, int l, int u){
if(l >= u)
return;
// 1. 随机选定轴元素并交换到数组首位置
swap(x, l, l + (int)rand(l - u));
int t = x[l], i = l, j = u + 1;
for(;;){
do { i++; } while (i <= u && x[i] < t);
do { j--; } while (x[j] > t);
if(i > j)
break;
swap(x, i, j);
}
swap(x, l, j);
qsort2(x, l, j-1);
qsort2(x, j+1, u);
}
最后，由于快速排序基于递归，而递归是有额外的性能损耗的，因此在数组被分割到一定的规模时，使用插入排序的效率会比继续使用递归快排要更高效。具体是多大的规模则需要按照具体场景进行统计得出。
void qsort2(int* x, int l, int u, int cutoff){
if(u - l < cutoff){
// 1. 当数组规模小于 cutoff 时使用上一节的 isort 2 插入排序
isort2(x + l, u - l + 1);
return;
}
swap(x, l, l + (int)rand(l - u));
int t = x[l], i = l, j = u + 1;
for(;;){
do { i++; } while (i <= u && x[i] < t);
do { j--; } while (x[j] > t);
if(i > j)
break;
swap(x, i, j);
}
swap(x, l, j);
qsort2(x, l, j-1);
qsort2(x, j+1, u);
}
注意：按照书中习题的思路可以进一步优化快速排序的性能。
1.3 小结
通过学习作者对排序算法的优化，发现书中设计的算法实现都非常精简，在保证了算法逻辑实现的同事，还避免了不必要的局部变量和冗余的判断条件。在平时自己写快速排序算法的时候经常避免不了这些问题。这恰恰体现的是一个程序员的功底。总之，爱因斯坦的那句名言还是适用：任何事情都应尽量简单，但不宜过于简单。
二、取样问题
取样是指从大量的数据样本中，随机提取一部分样本，作为数据分析的目标。这个问题乍一看好像很简单，生成抽样数量的随机数，然后按样本总规模取模不就可以了嘛。然而并不如此，因为这种方式生成的随机数，其原理相当于抽奖时采用可放回式的方式，这明显是不公平的，也就是说每种抽样集合的出现概率是不均匀的。而且若要求抽中的样本集有序，则难度会进一步增加。
取样问题是有一定复杂度的，一蹴而就还是有一定难度的，所以先思考一个简单的、具体化的例子。例如，以均匀的概率从 5 个样本中随机采集 2 个样本。定义以下两个事件：
- 事件 A：第 1 个样本被抽中；
- 事件 B：第 2 个样本被抽中；
根据条件概率公式 P(B|A) = P(BA)/P(A)，可以推导出两个条件概率：
- P(B|A)：第 1 个样本被抽中时（条件），第 2 个样本被抽中的概率（条件概率）；
- P(B|!A)：第 1 个样本不被抽中时（条件），第 2 个样本被抽中的概率（条件概率）；
P(B|A) = P(BA)/P(A) = (1/C(5,2))/(2/5) = (1/10)/(2/5) = 1/4 P(B|!A) = P(B!A)/P(!A) = (3/C(5,2))/(3/5) = (3/10)/(3/5) = 1/2
其中 !A 表示事件 A 的反面事件，即 P(!A) = 1 - P(A)；C(5,2) 表示从 5 个对象中选取 2 个对象的组合数。P(BA) 表示第 1、2 个样本都被抽中的概率，抽中事件的总数是 C(5, 2)，而同时抽中样本 1、2 的事件只有一种情况 (1, 2)，由于需要满足均匀概率的前提条件，因此每种组合事件的概率必须相等，因此 P(BA) = 1/C(5,2)；同理 P(B!A) 表示抽中样本 2 但未抽中样本 1 的概率，事件有三种情况 (2, 3)、(2, 4)、(2, 5)，因此 P(B!A) = 3/C(5,2)。
上面的概率推导过程乍一看可能感觉怪怪的，但实际上是合理的。就像年会抽奖时，不放回式抽取就是一种均匀概率抽样方法，在抽奖过程中不难发现以下规律：
- 规律一：随着中奖者的逐步揭晓，后续尚未中奖的同事中奖的概率会越来越低，因为剩余中奖名额正在逐步递减（P(B|A) < 2/5）；
- 规律二：若有同事退出抽奖（例如抽到某个领导，领导说把机会留给其他同事吧），则剩余未中奖的同事中奖的概率会得到提高（P(B|!A) > 2/5）；
2.1 Knuth随机抽样方法
接下来我们以上面的例子为基础，推导一种通用的随机抽样方式。抽样方式是遍历整个样本集，对每个元素模拟一次随机抽取操作，从规模为 n 的样本集 [0...n-1] 中抽取 m 个样本，则需要保证每个样本被抽中的概率都是 m/n。
当模拟样本 i 的随机抽取事件时，定义以下两个事件：
- 事件 U：已经抽取了 x 个样本剩余 m - x 样本需要抽取；
- 事件 V：样本 i 被抽中；
P(B|A) 为模拟样本 i 的随机抽取事件时应指定的抽中概率。仍然基于条件概率公式 P(V|U) = P(VU)/P(U)。我们通过分别计算 P(VU) 和 P(U) 来计算该条件概率，然后根据该条件概率编写模拟抽样的程序。P(UV) 的含义是，抽取样本中包含 i 样本，从 [0...i-1] 样本中抽取 x-1 个样本。基于每种抽中的集合的出现概率严格相等的前提条件，因此重点是计算 UV 事件的集合的事件数，可以用组合来表示 C(i,x)*C(n-i,m-x)，而集合的所有事件总数为 C(n,m)，因此可以计算 P(U)：
P(U) = C(i,x)*C(n-i,m-x)/C(n,m)
然后按照同样的原理计算 P(VU)：
P(VU) = C(i,x)*C(n-i-1,m-x-1)/C(n,m)
首先逐项消除多项式：
P(V|U) = P(VU)/P(U)
= (C(i,x)*C(n-i-1,m-x-1)/C(n,m)) / (C(i,x)*C(n-i,m-x)/C(n,m))
= C(n-i-1,m-x-1) / C(n-i,m-x)
= (A(n-i-1,m-x-1)/(m-x-1)!) / (A(n-i,m-x)/(m-x)!)
= (A(n-i-1,m-x-1)/A(n-i,m-x)) * ((m-x)!/(m-x-1)!)
= (1/n-i) * (m-x)
= (m-x)/(n-i)
上面的多项式中，A 表示排列，感叹号 ! 表示阶乘，C(n,m) = A(n,m) / m!。因此，当模拟到样本 i 的随机抽取事件时，应当设置其抽中概率为 P(V|U) = (m-x)/(n-i)，其中 m-x 为剩余可抽取样本数。抽样程序用几句代码就可以实现：
/** 其中 n 为样本规模，m 为抽样个数 */
void genknuth(int* samples, int n, int m){
// 1. remaining 为剩余抽取样本数量，初始化为 m
int remaining = m;
for(int i = 0; i < n; i++){
// 2. 对每个样本，以 remaining/(n-i) 的概率模拟抽样事件
if(rand() % (n-i) < remaining){
printf("%d", i);
remaining--;
}
}
}
以上算法最大的优点是简单，其次是耗费内存非常小。但是其时间复杂度是 O(n)，也就是说不管抽取的样本数量 m 的数量有多小，该算法的执行时长都是和样本总数成正比。
2.2 借助STL容器抽样
基于本节刚开始的简单随机抽样思路，通过数据结构层面的改进，实际上也是可以实现均匀概率抽样的。我们用Set集合的数据结构来保存抽样，当抽取到已存在于Set中的样本时，由于Set不保存重复元素，因此相当于将重复的样本丢弃，继续抽取，就像抽奖时，虽然是采用放回式，但是凑巧抽中已中奖的同事，则视为无效抽取，放回抽奖箱中继续抽。
#include <iostream>
#include <set>
using namespace std;
void gensets(int* samples, int n, int m){
set<int> S;
while(S.size() < m)
S.insert(random() % n);
set<int>::iterator i;
for(i = S.begin(); i != S.end(); ++i){
cout << *i << "\n";
}
}
由于Set数据结构插入效率是 O(LogN) 因此上述方法的时间复杂度是 O(mLogm)。对于 m 远小于 n 的情况，时间效率上会明显优于 Knuth 算法，但是该方法运行时需要借助Set数据结构保存和筛选抽中样本，其空间开销大于 Knuth 算法。
注意：C++ 的 STL 标准库中的
Set数据结构的实现是基于红黑树的平衡二叉检索树，保存的元素不重复，而且有序。
2.3 打乱前m个元素的顺序
从长度为 n 的集合中随机抽取 m 个样本，还可以通过随机打乱前 m 个样本的顺序获得。注意：打乱的过程是：对样本 i，随机在 [i, n) 半开区间范围内抽取一个样本 j，然后交换两者。之所以要先定 [i, n) 半开区间是因为在 i 之前的元素已被抽中，必须保证余下的未被抽中元素有同等的机会被抽中。其实现代码如下：
void genshuf(int* samples, int n, int m){
int i, j;
// 1. 用一个临时数组保存打乱的前 m 个元素的索引
int *x = new int[n];
for(i = 0; i < n; i++){
x[i] = i;
}
// 2. 模拟打乱过程
for(i = 0; i < m; i++){
j = random()%(n - i) + i;
int temp = x[i];
x[i] = x[j];
x[j] = temp;
}
// 3. 需要生成有序的样本集，因此需要排序
sort(x, x + m);
for(i = 0; i < m; i++){
cout << x[i] << "\n";
}
}
上述算法的时间复杂度是 O(n + mlogm)，空间复杂度是 n，因此在性能上通常还不如 Knuth 算法。对比gensets算法，则当 m 远小于 n 时时间效率更差，随着 m 的增大，两者的差距会越来越小，达到某个阈值时，genshuf算法事件效率会反超gensets。
注意：练习题中提出，当 m 越来越趋近于 n 时，
gensets算法的while循环迭代过程中，会丢弃越来越多的重复元素，因为元素已经存在与集合中。练习题的答案genfloyd算法使随机抽样次数严格控制在 m，在 m 趋近 n 时性能强于gensets但弱于genshuf，在 m 远小于 n 时性能不及gensets。
void genfloyd(int* samples, int n, int m){
set<int> S;
for(int j = n - m; j < n; j++){
int t = random() % (j + 1);
set<int>::iterator result = S.find(j);
if(result == S.end()){
S.insert(t);
}else{
S.insert(j);
}
}
set<int>::iterator i;
for(i = S.begin(); i != S.end(); ++i){
cout << *i << "\n";
}
}
2.4 小结
文章最后从解决随机抽样问题的过程总结出编程问题的解题思路。其实和之前的总结有相同之处，比较特别的地方是，作者这里强调了解决问题最好考虑尽可能多的可选方案，从中择优：
- 正确理解所遇到的问题；
- 提炼出抽象问题；
- 考虑尽可能多的解法；
- 实现一种解决方案：如果在前一阶段能评估出某种算法的性能明显优于其他选项，就可以只实现该最优算法，如果不能确定则实现几个可选方案并在运行中对比其性能；
- 回顾：回顾问题的解决过程，确认是否还有改进的余地；
三、搜索
本章研究的搜索问题是：在没有其他相关数据的情况下，如何存储一组整数？乍一看好像问题没什么意义，不就是数组吗？但其实不然，作者揭示了其中很多的学问，主要是在数据结构层面上优化整数的搜索过程。
本章讨论的问题任然是上一章的随机抽取样本并按顺序输出的问题。不同点是：上一章直接使用cout输出抽取样本的索引，而本章则需要保存抽中样本索引到某个数据结构，然后输出。应该以什么数据保存这些样本数据，是本章讨论的核心问题。
3.1 准备工作
首先将随机抽样的程序抽象为类型，其接口定义如下：
class IntSetImp {
public:
/** 构造函数 */
IntSetImp(int maxelement, int maxval);
/** 插入随机抽取的样本，需要排除重复样本。 */
void insert(int t);
/** 抽中样本规模 */
int size();
/** 将抽中的样本保存到数据结构 v */
void report(int *v);
}
则上一章gensets的实现如下：
void gensets(int* samples,int m, int maxval){
int *v = new int[m];
IntSetImp S(m, maxval);
while (S.size() < m)
S.insert(random() % maxval);
S.report(v);
for(int i = 0; i < m; i++){
cout << v[i] << "\n";
}
}
那么基于集合的gensets的对应类的具体实现如下：
class IntSetSTL {
private:
set<int> S;
public:
IntSetSTL(int maxelement, int maxval){ }
int size(){ return S.size(); }
void insert(int t){ S.insert(t); }
void report(int *v){
int j = 0;
set<int>::iterator i;
for(i = S.begin(); i != S.end(); ++i){
v[j++] = *i;
}
}
}
上述IntSetSTL将抽中样本数据保存到set数据结构中，在report实现中，使用set的迭代器将抽中的样本索引写入数组v中。这种方法看起来还不错，但是还不够好，接下来看作者怎么给该算法“挤出”优化的空间。
3.2 线性结构方式
可以尝试使用线性结构来实现IntSetImp，由于insert操作需要去重，而report函数需要按需输出，因此使用线性结构保存的整数集合必须保证始终有序，也就是说插入时需要插入到正确位置。
使用数组数据结构，则需要两个数据x用于记录抽中数据样本，n用于记录样本数量，由于样本的值在 [0, n) 半开区间范围内，也就是说抽中样本的值一定小于n。在插入时，必须保证 x 数组始终有序，因此需要找到目标插入位置，然后将目标插入位置后面的所有元素向右平移一个单位，最后将抽中样本放入目标插入位置，因此整个过程的的时间复杂度是 m2。
class IntSetArray {
private:
int *x;
int n;
public:
IntSetArray(int maxelement, int maxval){
x = new int[1+maxelement];
n = 0;
x[0] = maxval;
}
int size(){ return n; }
void insert(int t){
int i, j;
for(i = 0; x[i] < t; i++);
if(x[i] == t)
return;
for(j = n; j >= i; j--){
x[j+1] = x[j];
}
x[i] = t;
n++;
}
void report(int *v){
for(int i = 0; i < n; i++){
v[i] = x[i];
}
}
};
使用链表数据结构，大致流程与数组一致，但是由于链表插入操作不需要元素平移过程，因此只要找到目标插入位置，将抽中样本插入即可。但是作者用了递归扫描的思路。实现代码如下：
class IntSetList {
private:
int n;
struct node{
int val;
node* next;
node(int v, node* p){
val = v;
next = p;
}
};
node* head;
node* sentinel;
public:
IntSetList(int maxelement, int maxval){
n = 0;
head = sentinel = new node(maxval, NULL);
}
int size(){ return n; }
void insert(int t){
head = rinsert(head, t);
}
node* rinsert(node* p, int t){
if(p->val < t){
p->next = rinsert(p->next, t);
}else if(p->val > t){
p = new node(t, p);
n++;
}
return p;
}
void report(int *v){
int j = 0;
for(node* p = head; p != sentinel; p = p->next){
v[j++] = p->val;
}
}
};
注意：上述算法实现过程中引入一个
sentinel指针，这是个哨兵元素，用于标记链表的尾节点，其值设置为maxval临界值，引入哨兵元素经常可以简化算法的实现。
上述rinsert递归函数的处理逻辑是：
- 当前扫描节点的值等于目标插入值时，返回当前扫描节点（因为说明集合中已经存在目标插入值就无需插入操作了）；
- 当前扫描节点的值大于目标插入值时，新建一个节点，将新节点值指定为目标插入值，新节点的
next指向当前扫描节点（因为需要在当前扫描节点之前插入目标插入值），然后递增集合的长度n，并返回新节点。注意，走到这一步时当前扫描节点的上一个节点的next是指向当前扫描节点的，为了完成插入，还需要将其修正为指向新节点才完成完整的插入操作； - 当前扫描节点的值小于目标插入值时，将当前扫描节点的
next指向rinsert(p->next, t)的返回值，递归的出口就是上面两个分支，因此当rinsert(p->next, t)插入新元素并返回新元素时（分支二），则恰好完成了新元素插入操作；
插入的逻辑实际上比较简单，完全可以将其转化为非递归过程，从而在一定程度上提升运行速度，代码如下，需要借助pre变量，记录当前扫描节点的上一个节点。
void insert(node* head, int t){
node* p = head, *pre = NULL;
while(p->next && p->val < t){
pre = p;
p = p->next;
}
if(!p->next){
// 接到 p 后面
p->next = new node(t, NULL);
}else if(p->val > t){
// 接到 pre 后面 p 前面
pre->next = new node(t, p);
}
// else{
// // p->val == t 无需插入
// }
}
3.3 二叉排序树方式
前面用标准模板库set数据结构实际上是使用了红黑树的数据结构保存数组，由于红黑树插入还需要平衡过程，因此可以考虑使用自定义的二叉排序树保存抽中样本，不考虑平衡性。速度会稍微快于set方式。
注意，由于遍历二叉树并输出到数组的过程使用前序遍历递归实现，因此必须要设置一个全局变量记录当前遍历到的元素索引，因此这里在类中，额外定义了v指针指向遍历输出的数组，vn用于记录当前遍历到的元素索引。
class IntSetBST{
private:
int n;
// 用于遍历
int* v;
int vn;
struct node{
int val;
node* left;
node* right;
node(int i){
val = i;
left = NULL;
right = NULL;
}
};
node* root;
public:
IntSetBST(int maxelement, int maxval){
n = 0;
root = NULL;
}
int size(){ return n; }
void insert(int t){
root = rinsert(root, t);
}
/** 典型的二叉排序树递归插入 */
node* rinsert(node* p, int t){
if(p == NULL){
root = new node(t);
n++;
}else if(t < p->val){
rinsert(p->left, t);
}else if(t > p->val){
rinsert(p->right, t);
}
return p;
}
void report(int *x){
v = x;
vn = 0;
traverse(root);
}
/** 典型的二叉树前序遍历 */
void traverse(node* p){
if(p == NULL)
return;
traverse(p->left);
v[vn++] = p->val;
traverse(p->right);
}
};
上述代码中节点的内存分配是离散的，可以一次性分配所有节点到连续的内存空间，从而提高程序的整体运行效率。
3.4 用于整数的数据结构
也可以考虑用第一章介绍的位图方式保存抽中样本，但是有个问题，由于随机抽中的样本可能非常稀疏，所以内存空间浪费可能会非常严重。可以稍作改进以提高内存利用率。试想，如果从 1 000 000 个样本随机抽取 1000 个样本，可以尝试使用 1000 长度的数组保存 1000 个区间的抽中样本，例如，数组的索引 0 保存 [0, 1000) 范围内的抽中样本，索引 1 保存 [1000, 2000) 范围内的抽中样本，以此类推。由于抽样是随机的，因此每个区间内的抽中样本的期望长度是 1。当然会有多个样本落到一个区间内的情况，因此只用一个数组保存是不够的，应该在数组的每个索引保存一个链表的地址，链表中保存落入该区间的所有样本，而且链表的节点的值是有序的。这种方式叫做箱。
class IntSetBins {
private:
int n;
int bins;
int maxval;
struct node{
int val;
node* next;
node(int v, node* p){
val = v;
next = p;
}
};
node** bin;
node* sentinel;
public:
IntSetBins(int maxelement, int maxval){
n = 0;
bins = maxelement;
bin = new node*[bins];
sentinel = new node(maxval, NULL);
for(int i = 0; i < bins; i++){
bin[i] = sentinel;
}
}
int size(){ return n; }
void insert(int t){
int i = t / (1 + maxval/bins);
bin[i] = rinsert(bin[i], t);
}
/** 链表插入的递归方式实现 */
node* rinsert(node* p, int t){
if(p->val < t){
p->next = rinsert(p->next, t);
}else if(p->val > t){
p = new node(t, p);
n++;
}
return p;
}
void report(int *v){
int j = 0;
for(int i = 0; i < bins; i++){
for(node* p = bin[i]; p != sentinel; p = p->next){
v[j++] = p->val;
}
}
}
};
上述代码中节点的内存分配是离散的，可以一次性分配所有节点到连续的内存空间，从而提高程序的整体运行效率。消除递归可以进一步提升程序的运行效率。箱方式的时间效率是最高的。
3.5 小结
- 库的作用：使用 C++ 通用模板库可以以最快的速度实现算法，而且也有一定的性能保证，但是通用库并不是唯一的、最好的选择，例如上面自定义的二叉排序树数据结构、箱方式的运行效率都要高于使用
set的实现； - 空间的重要性：如果简单地使用离散方式分配链表的节点，实际占用内存可能会高于理论计算值，由于地址空间离散，访问效率也低于连续分配。上文中提到使用内存统一、连续的分配方式可以提高内存的利用率，以及内存中的数据访问速度；
- 代码调优方法：本章用到的调优方式包括消除递归、统一分配内存空间。引入哨兵可以简化算法的实现也十分具有借鉴意义；
四、堆
堆是一个完全二叉树结构。完全二叉树可以保存在一个数组结构中，利用节点在数组中的索引之间的数值关系来表示，节点之间的父子关系。完全二叉树的节点在其对应的数组中的排列原则是，由根节点开始，从上到下从左到右，将节点逐层放置到数组中，例如：下图一的完全二叉树，使用数组表示为图二中的数组。注意，数组使用的索引是从 1 开始的。
因此可以非常简单的总结出：
- 在数组中索引为 i 的节点的父节点为数组中索引为 i/2 的节点，当 i/2 为零表示节点 i 为根节点；
- 在数组中索引为 i 的节点的左子节点为数组中索引为 2i+1 的节点；
- 在数组中索引为 i 的节点的右子节点为数组中索引为 2i+1 的节点；
堆有两种：
- 大顶堆：任何节点的值都小于或等于其父节点的值；
- 小顶堆：任何节点的值都大于或等于其父节点的值；
判断一个数组是否为小顶堆，可以用以下递归过程实现（大顶堆同理）：
/** 判断数组是否为小顶堆 */
bool risminheap(int* x, int length, int i){
// 1. 空树也是堆，索引超出范围也直接返回 true
if(!x || length < 1 || i >= length)
return true;
// 2.1 如果存在左子节点且左子节点的值小于该节点的值，则直接判断不是小顶堆
if(2*i < length && x[2*i] < x[i])
return false;
// 2.2 如果存在右子节点且右子节点的值小于该节点的值，则直接判断不是小顶堆
if(2*i + 1 < length && x[2*i + 1] < x[i])
return false;
// 3. 递归判断左子树和右子树也是小顶堆
return risminheap(x, length, 2*i) && risminheap(x, length, 2*i + 1);
}
注意：为统一代码实现，本章接下来所说的堆都是小顶堆。
4.1 两个关键函数
堆有两个关键操作：
- 在现有堆的基础上，插入元素，涉及的关键函数是上滤（
siftup）； - 在现有堆的基础上，移除根节点，涉及的关键函数是下滤（
siftdown）；
上滤
堆上滤过程比较简单。插入节点时：
- 首先将元素插入堆的结尾；
- 然后将插入元素和父节点比较，若插入元素比父节点的值小，则交换插入节点与父节点的位置；
- 重复第二步操作，直到插入元素大于等于父节点的值为止；
因此，在现有堆的基础上，插入元素并完成插入元素的上滤操作后，数组仍然是堆。由于小顶堆的父节点一定小于等于子节点的值，因此每次判断是否需要交换时，只需要和父节点比较，不需要和兄弟节点比较，因为插入元素值比父节点小，就一定比兄弟节点小。举个具体的例子，如下图所示：
上滤操作的实现代码如下：
/** 上滤，其中 n 表示堆的元素总数 */
void siftup(int* x, int n){
int i = n;
while(i != 1 && x[i/2] <= x[i]){
// 交换
int temp = x[i];
x[i] = x[i/2];
x[i/2] = temp;
i /= 2;
}
}
下滤
堆下滤操作比上滤稍微复杂一点点。删除堆的根节点时：
- 首先将根节点移除，并将堆的最后一个元素移动到根节点处；
- 然后比较根节点与左右子节点的值较小者进行比较，若根节点更大，则交换根节点与左右子节点的值较小者的位置；
- 重复第二步操作，直到元素值均小于等于左右子节点的值为止；
同样，在现有堆的基础上，移除元素并将堆最后一个元素交换到根节点，完成根节点的下滤操作后，数组仍然是堆。举个具体的例子，如下图所示：
下滤操作的实现代码如下：
/** 下滤，其中 n 表示堆的元素总数 */
void siftup(int* x, int n){
int i = 1;
do{
int c = 2*i;
if(c > n)
break;
if(c + 1 < n && x[c+1] < x[c]){
c++;
}
if(x[i] <= x[c])
break;
int temp = x[i];
x[i] = x[c];
x[c] = temp;
i = c;
}while(1);
}
4.2 优先级队列
优先级队列是初始为空的元素集合，仅包含弹出优先级最高任务以及插入特定优先级的任务两种基本操作的数据结构。很明显，优先级队列非常适合使用堆来实现。弹出优先级最高任务需要用到下滤操作，插入插入特定优先级的任务则需要用到上滤操作，只要保证优先级队列的始终为堆，则插入删除都只要 O(LogN) 的时间复杂度。
4.3 堆排序
利用堆可以实现排序算法，其主体过程是：
- 首先，以空堆为起始，将目标排序集合的所有元素逐一插入到堆中（上滤），这个过程也叫建堆；
- 然后，将根节点交换到数组末端，此时在数组右端形成有序区，交换完成后，需要对新的根节点进行下滤操作；
- 最后，重复第二步直到有序区扩展到整个数组；
下图是建堆后，如果通过根节点移除操作，逐渐在数组右端形成有序区的过程（只展示了前三次迭代，后面的以此类推）：
首先实现建堆函数：
void buildheap(int* x, int n){
for(int i = 2; i <= n; i++){
siftup(x, i);
}
}
然后实现堆排序：
void hsort(int* x, int n){
buildheap(x, n);
for(int i = n; i >= 2; i--){
swap(1, i);
siftdown(x, i - 1);
}
}
实际上，可以合并上述两个函数的实现，整个堆排序算法的代码合起来也只有五句：
void hsort1(int* x, int n){
for(int i = 2; i <= n; i++){
siftup(x, i);
}
for(int i = n; i >= 2; i--){
swap(1, i);
siftdown(x, i - 1);
}
}
4.4 小结
- 高效性：堆的上滤下滤操作的时间复杂度是 O(LogN) 十分高效；
- 正确性：堆的上滤下滤等操作函数的正确性，需要建立在操作之前数据是堆结构，且操作完成后数据仍然为堆的前提下，这是堆数据结构的不变式；
- 抽象性：好的程序员在程序设计阶段就可以对功能组件做一个很好的抽象，抽象包括过程抽象和抽象数据类型。例如本章中
siftup函数和siftdown函数可以应用到优先级队列和堆排序中，在使用时无需关心其具体实现，这是一种过程抽象；上一章中对IntSet的各种具体实现体现的是，抽象数据类型定义的重要性。
五、字符串
本章讨论的时字符串的各种操作，例如排序、统计、搜索以及分析它们以区分不同的模式等等。通过一些有关字符串的经典问题来讨论这些操作。
5.1 单词
STL Map
第一个问题是统计圣经中出现的所有单词的频率。使用 C++ STL 库的map数据结构实现的代码如下：
#include <iostream>
#include <map>
void countWords(){
map<string, int> M;
map<string, int>::iterator j;
string t;
while (cin >> t) {
M[t]++;
}
for(j = M.begin(); j != M.end(); ++j){
cout << j->first << " " << j->second << "\n";
}
}
哈希表
C++ STL 库的map数据结构实现是基于红黑树，因此上述算法的执行效率比较高。但是还不够高，使用哈希表结构可以进一步提升算法的执行效率。
首先定义散列表的链表节点类型（拉链法解决哈希冲突）：
/** 哈希表的数组主体的元素类型为链表地址 */
typedef struct hnode* hnodeptr;
/** 哈希表的数组主体的元素所指向的链表的元素类型 */
typedef struct hnode {
/** 单词。键 */
char* word;
/** 单词计数。值 */
int count;
/** 下一个节点 */
hnodeptr next;
}hnode;
然后定义哈希函数：
/** 哈希表大小 */
#define NHASH 29989
/** 哈希函数用到的常数 */
#define MULT 31
/** 哈希表主体为数组，数组元素为 hnode 的指针，表示链表地址 */
hnodeptr bin[NHASH];
/** 哈希函数 */
unsigned int chash(const char* p){
unsigned int h = 0;
for(char* q = (char*)p; *q; q++){
h = MULT * h + *q;
}
return h % NHASH;
}
再定义单词计数函数：
void incword(const char* p){
// 1. 计算哈希索引
int h = chash(p);
// 2. 若 word 存在于哈希表中，递增 word 计数
for(hnodeptr q = bin[h]; q != NULL; q = q->next){
if(strcmp(q->word, p)){
q->count ++;
return;
}
}
// 3. 若 word 不存在于哈希表中则先构建 hnode 实例
hnodeptr q = (hnodeptr)malloc(sizeof(hnode));
q->count = 1;
q->word = (char*)malloc(strlen(p) + 1);
strcpy(q->word, p);
// 4. 将新构建的 hnode 实例插入到相应的链表头部
q->next = bin[h];
bin[h] = q;
}
最后整个单词统计函数的实现如下：
void countWords1(){
string t;
while (cin >> t) {
incword(t.c_str());
}
for(int i = 0; i < NHASH; i++){
for(hnodeptr p = bin[i]; p; p = p->next){
cout << p->word << " " << p->count << "\n";
}
}
}
哈希表查找、插入的时间复杂度是 O(1)，在效率上会比 STL 库的map高出一个数量级。散列的速度很快，但是散列表是无序的，且缺乏平衡树的提供的最坏情况性能保护。
5.2 短语
本节讨论的问题是：给定一个文本文件作为输入，查找其中最长的重复字符串。例如：“Ask not what your country can do for you, but what you can do for your country”中最长的重复字符串是“can do for you”。这其实是短语搜索匹配的过程。
穷举
首先尝试以最直观的方式解决该问题。对于长度为 n 的字符串 x，选取两个子串 x[i, n) 和 x[j, n]，其中 i < j，检测以 i，j 为起始的子串的最大匹配长度，遍历所有 i，j 即可得出结果。匹配的原理如下图所示，其中绿色标记区域为以 i，j 为起始的子串，红色为匹配区域。
检测最大匹配长度的函数如下：
int complen(char* p, char* q){
int i = 0;
while(*p && *p++ == *q++)
i++;
return i;
}
最后解决该问题的算法如下：
char* maxRepeatSubstring(char* c){
int maxlen = -1;
char* substring = NULL;
for(char* p = c; *p; p++){
for(char* q = p + 1; *q; q++){
int thislen = complen(p, q);
if(thislen > maxlen){
maxlen = thislen;
substring = p;
}
}
}
if(maxlen < 1)
return NULL;
char* output = (char*)malloc(maxlen + 1);
memcpy(output, substring, maxlen);
return output;
}
后缀数组
上述算法需要嵌套两层子串扫描过程，因此复杂度至少在 n2 以上。实际上还有更好的解决该问题的方法，就是借助后缀数组。
后缀数组保存字符串的所有后缀子串。例如，对于长度为 n 的字符串 x，其后缀数组的长度也是 n，保存的元素是&x[0]、&x[1]、&x[2]...&x[n-1]。例如，字符串 "banana" 的后缀数组的定义如下图所示，箭头表示指向字符串的字符的地址。
那么 "banana" 的后缀数组p的每个元素所指向的x字符串的子串分别为：
p[0] -- &x[0] -- "banana"
p[1] -- &x[1] -- "anana"
p[2] -- &x[2] -- "nana"
p[3] -- &x[3] -- "ana"
p[4] -- &x[4] -- "na"
p[5] -- &x[5] -- "a"
如果对后缀数组进行排序，则以最长的重复字符串为前缀的后缀子串必定彼此相邻。例如对上述后缀数组 p 进行排序后得到：
"a"
"ana"
"anana"
"banana"
"na"
"nana"
只要遍历一次后缀数组使用前面定义的complen函数即可得到 "banana" 最长重复字符串为 "ana"。因此算法的主流程是：
- 构建后缀数组；
- 后缀数组排序；
- 遍历后缀数组，并调用
complen检测相邻元素的最长匹配前缀； - 遍历完成得到结果；
后缀数组方式的优势是更低的时间复杂度，但是运行过程中需要保存后缀数组，需要借助 n 长度的内存空间。
5.3 生成文本
本章介绍的算法结合了字符串比较、排序、二分搜索、随机抽样、后缀数组等元素，解决了一个输入大量具有语义的参考文本，并根据输入文本随机生成文本的问题。基本上是前面介绍的方法的简单组合。
（略）
5.4 小结
- 散列表：散列表也叫哈希表，O(1)的插入以及查找复杂度，快是其最大的优势，劣势在于需要分配冗余的空间以保证散列表性能，且散列表的元素是无序的。哈希表实际也上也可以构建最坏情况保护机制，例如当冲突数量超过一定阈值时进行重哈希或扩容；
- 平衡树：C++ STL 库的
set和map实现基于红黑树，自带平衡机制，这些结构在最坏情况下也具有较好的性能； - 后缀数组：这个数据结构很有用；
