《编程珠玑》第11、12、13章读书笔记
第三部分 应用
第11章 排序
问题：使用库排序函数并非总是有效的，因此在某些情况下程序员要自己编写排序函数。
插入排序：大多纸牌游戏的玩家都采用插入排序来排列手中的纸牌。他们保持已发到手中的牌有序，当拿到一张新牌时，即将其插入合适的位置，
伪代码：
for i = [1,n)
/* invariant: x[0..n-1] is sorted */
/* goal: sift x[i] down to its proper place in x[0..i] */
完整的程序：
for i = [1,n)
for(j = i; j > 0 && x[j-1] > x[j]; j--)
swap(j-1,j)
优化考虑：
>>swap函数调用
直接将函数体写入内循环。（许多优化编译器会实现该功能）
[加速系数= 3]
for i = [1,n)
for(j = i; j > 0 && x[j-1] > x[j]; j--)
{
t = x[j]; x[j] = x[j-1]; x[j-1] = t;
}
>>内循环的t重复赋值
将两个含t的赋值语句移出内循环，减少重复的赋值步骤。
[加速系数= 1.15]
for i = [1,n)
{
t = ***>
for(j = i; j > 0 && x[j-1] > x[j]; j--)
{
x[j] = x[j-1];
}
x[j-1] = t;
}
最坏情况下，该算法的运行时间与n2成正比，而如果输入数组几乎是有序的，那么每个元素移动的距离都很短，插入排序的速度会快很多；
伪代码：递归结束的条件是待排序部分的元素个数小于2.
void qsort(l,u)
if(l >= u) then
/* at most one element, do nothing */
Return
/* goal: partition array around a particular value, which is eventually placed in its correct postion p */
qsort(l,p-1)
qsort(p+1,u)
优化考虑：
>>双向划分: 避免非随机输入时快速排序的性能差的问题
假设i和j是待划分数组的两端，主循环中有两个内循环，第一个内循环将i向右移过小元素，遇到大元素时停止；第二个内循环将j向左移过大元素，遇到小元素时停止，然后主循环判断两个下标是否交叉并交换他们的值。
[最坏情况 ： nlog2n]
A:当元素相同时代码如何处理呢？当遇到相同元素时停止扫描，并交换i和j的值。这样做交换次数增加了，但将所有元素都相同的最坏情况变成了差不多需要nlog2n次。
B:如果数组已经按升序排好了，可以通过随机选择划分元素提交性能。swap(l, randint(l,u))；
C:可使用插入排序来排序很小的子数组提高效率。设置cutoff阈值，其确定可以通过对比其在[1,100]上每个可能取值的运行时间来确定。
D：展开循环体内的swap函数的代码
>>swap函数调用
同上一节。
完整代码：
void qsort4(l,u)
if u - l < cutoff
return
swap(l, randint(l,u))
t = x[l]; i = l; j = u + 1
loop
do i++; while i <= u && x[i] < t
do i--; while x[i] > t
if(i > j)
break;
temp = x[i]; x[i] = x[j]; x[j] = temp;
swap(l,j)
qsort4(l, j-1)
qsort4(j+1, u)
C++标准库函数sort由于具有最简单的接口，平均运行时间最少；
本章针对随机取样问题，讨论了解决问题的一般思路。
问题描述：假设有一个能返回很大的随机整数（远远大于n,m）的函数bigrand(),以及一个能返回i..j范围内均匀选择的随机整数的函数randint(i,j),如何实现选择并输出0~n-1范围内的m个随机整数的有序列表。从概率的角度，希望没有重复的有序选择，其中每个选择出现的概率相等。
方法1：Knuth通过概率证明的方法（按序访问整数，可保证输出结果有序。）（从r个剩余的整数中选出s个，可以以概率s/r选择下一个数。）
完整代码：
void genknuth(int m , int n){
for(int i = 0; i < n; i++)
/* select m of remaining n-i */
if((bigrand() % (n-i)) < m){
cout << i << “\n”
m--;
}
}
算法的运行时间和n成正比。
方法2：在一个初始集为空的集合内插入随机整数，直到个数足够（利用C++标准模板库，用set表示集合）
完整代码：
void gensets(int m , int n){
set<int> S;
while(S.size() < m)
S.insert(bigrand() % n);
set<int>::iterator i;
for(i = S.begin; i != S.end(); ++i)
cout << *i <<”\n”;
}
插入操作时间复杂度为O(longm),遍历集合需要O(m),所以完成程序时间复杂度为O(mlogm)；但是该数据结构空间开销比较大。
方法3： 打乱包含n个元素的数组顺序，前m个元素排序输出即可
void genshuf(int m , int n){
int i, j;
int *x = new int[n];
for(int i = 0; i < n; i++)
x[i] = i;
for(int i = 0; i < m; i++){
j = randint(i, n-1);
int t = x[i]; x[i] = x[j]; x[j] = t;
}
for(i = 0; i < m; i++)
cout << x[i] <<”\n”;
}//空间O(n),时间O(n+mlogm)
这一方法需要O（n）的空间与时间。
其他解决方案概述：
A:当n比较大，并且m和n比较接近时，可以生成（n-m）个有序随机样板，然后输出不在样本中的整数。
本章主要介绍，存储按序输出的容器或者说存放集合的方法。并实现按序插入，按序输出。
1）set容器 set<int> S;（接口）
set容器实现插入元素，并有序输出；
class IntSetSTL{
private：
set<int> S;
public:
IntSetSTL(int maxelements, 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;
}
}
2）数组（类似于插入排序）（线性结构：事先知道集合大小）
思路：初始化时候，取一个很大元素作为哨兵，哨兵永远置于元素最后。
插入时候遇到重复元素，返回；
遇到比自己大的第一个元素，将该元素以及以后的元素后移一位，最后将该元素插入该位置；
3）链表（线性结构：事先不知道集合大小）
思路1：【递归】调用的时候，p->next=rinsert(p->next,t);如果p-val > t则p =new node(t,p)
说明第一个大于t的p被作为新节点（val=t）的next
思路2：【存储分配】构造函数只分配一个具有m个结点的块，insert根据需要使用这些空间；而不是每次插入分配一个新的结点
时间开销：存储分配的时间开销要比大多数简单运算高出两个数量级；
空间开销：若将多个结点分配为一个块，每个结点8个字节；若分别为这些结点分配空间，每个结点48个字节；
思路3：【链表非递归】主要是找到第一个大于t的节点，然后插入到其前面。
提高效率的方法：高速缓存（加速系数1.1）和消除递归（加速系数为5）。
链表结构效率比数组低的原因：大链表必须将8字节的结点读入高速缓存以访问4字节的整数，另外数组访问数据时具有较好的预见性，而链表的访问模式则可能导致在内存空间的来回跳跃。
4）二分搜索树（类似链表）
如果事先知道集合的大小，那么数组这种结构来比较适合实现集合。因为数组是有序的，所以能用二分查找建立一个运行时间为O(logn)的成员函数。
简单的二分查找树避免了STL所使用的复杂的平衡方法，因此，它会稍微快一些，同时使用的空间也更少一些。最重要的是它一下子就分配所有的结点。（自己管理分配）这就大大降低了树的空间需求，运行时间降低了。
5）专门用于整数处理的数据结构
位向量的私有数据和函数：
enum { BITSPERWORD = 32, SHIFT = 5, MASK = 0x1F };
int n, hi, *x;
void set(int i) { x[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { x[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i) { return x[i>>SHIFT] & (1<<(i & MASK)); }
IntSetBitVec(int maxelements, int maxval)
{ hi = maxval;
x = new int[1 + hi/BITSPERWORD];
for (int i = 0; i < hi; i++)
clr(i);//所有的位都置零
n = 0;
}
int size() { return n; }
void insert(int t)
{ if (test(t))
return;
set(t);
n++;
}
void report(int *v)
{ int j=0;
for (int i = 0; i < hi; i++)
if (test(i))
v[j++] = i;
}
结合链表和位向量的优点，每一个箱表示一定范围的整数，并用链表链接起来。链表插入采用有序插入；
int n, bins, maxval;
struct node {
int val;
node *next;
node(int v, node *p) { val = v; next = p; }
};
node **bin, *sentinel;
void insert(int t){ int i = t / (1 + maxval/bins); //安全映射到某个箱子中
bin[i] = rinsert(bin[i], t); //类似于前面链表中的rinsert
}
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;
}
小结：库的作用：当涉及数据结构问题时，可以使用库函数解决特定问题，提高运行速度。
空间的重要性：链表因为非顺序存储，效率比数组更低。
代码调优方法：分配大的内存块替代通用的内存分配。
#笔记##读书笔记#