第二章
首先讲了最基础的插入排序（虽然浩强哥的书基础的是冒泡和选择），然后讲到了分治：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归的解决这些子问题，然后再合并其结果，就得到原问题的解。
分治策略的三步骤(P17)：分解(Divide)，解决(Conquer)，合并(Combine)。
对算法，如果在最坏情况下运行时间比另一个算法的低，我们就常常认为此算法效率更高。
插入算法实现如下：
void InsertSort(vector<int> &v)
{
int temp;
for (int i=1 ; i < v.size() ; i++)
{
if (v[i] < v[i-1])//需要插入了
{
temp = v[i];
for (int j=i-1 ; v[j] > temp ; j--)
v[j+1] = v[j];//后移
v[j+1] = temp;
}
}
}
void BInsertSort(vector<int> &v)
{//折半插入
int temp;
for (int i=1 ; i<v.size() ; i++)
{
int low=0,high=i-1;
temp = v[i] ;
while (low <= high)
{
int mid = (low+high)/2 ;
if (temp < v[mid] ) //插入位置在低半段
high = mid-1;
else
low =mid+1;
}
for (int j=i-1 ; j>=high+1 ; j--)//high+1到i-1，后移
v[j+1] = v[j];
v[high+1] = temp;
}
}
void reverseInsert(vector<int> &v , int n)
{//递归插入,到1w会stack overflow
if (n==0)
v.push_back(v[0]);
else
{
reverseInsert(v,n-1);
//插入n到有序的n-1大的v中
int temp = v[n] ;
int low=0,high=n-1;
while (low <= high)
{
int mid = (low+high)/2 ;
if (temp < v[mid] ) //插入位置在低半段
high = mid-1;
else
low =mid+1;
}
for (int j=n-1 ; j>=high+1 ; j--)//high+1到i-1，后移
v[j+1] = v[j];
v[high+1] = temp;
}
}
第一个为直接插入排序，缺点是比较次数可能过多，因此，第二个折半插入，首先折半查找插入位置，再插入，可明显减少比较次数；第三个为插入排序的递归版，是练习题2.3-4，存在的问题是，当元素超过1w时会stack overflow。 递归插入，思路是，要排序A[1....n]，先插入排序A[1...n-1]，然后再将A[n]插入到已排序数组A[1.....n-1]中。
经过测试，折半插入稍稍快于递归插入，不过不明显，不过他们都明显快于直接插入。
对测试文件的说明：由于用数组方式，到较大数字会stack overflow，所以用了vector替代数组；又因为数组方式，数组名相当于指针，地址传参方式可以进行正确排序修改，而vector则必须添加引用。
归并排序实现如下：
void Merge(vector<int> &v ,int low ,int mid , int high)
{//归并过程,用哨兵
int n1=mid-low+1; //前半段
int n2=high-mid; //后半段
vector<int> L,R;
int i,j , k;
for (i=0 ; i<n1 ; i++) //分别复制上下半段
L.push_back(v[low+i]);
for (i=0 ; i<n2 ; i++)
R.push_back(v[mid+i+1]);
L.push_back(INT_MAX);//设置个无穷大哨兵元素，方便后面的比较
R.push_back(INT_MAX);
for ( k=low ,i=0,j=0 ; k <= high ; k++)
{
if (L[i] <= R[j])
v[k] = L[i++];
else if (R[j] < L[i])
v[k] = R[j++];
}
}
void MergeNo(vector<int> &v ,int low ,int mid , int high)
{//不使用哨兵
int n1=mid-low+1; //前半段
int n2=high-mid; //后半段
vector<int> L,R;
int i,j , k;
for (i=0 ; i<n1 ; i++) //分别复制上下半段
L.push_back(v[low+i]);
for (i=0 ; i<n2 ; i++)
R.push_back(v[mid+i+1]);
for ( k=low ,i=0,j=0 ; i<n1 && j< n2; k++)
{
if (L[i] <= R[j])
v[k] = L[i++];
else if (R[j] < L[i])
v[k] = R[j++];
}//for
if (i<n1)
for (int m=0 ; m<n1-i ; m++) //把i到mid这段的复制过去
v[k+m] = L[i+m];
if (j<n2)
for (int m=0 ; m<n2-j ; m++)
v[k+m]=R[j+m];
}
void MergeSort(vector<int> &v,int low ,int high)
{//递归排序
if (low < high)
{
int mid = (low+high)/2;
MergeSort(v,low,mid);
MergeSort(v,mid+1,high);
// Merge(v , low , mid ,high) ;
MergeNo(v,low,mid,high);
}
}
其中第一个采用哨兵元素，伪代码见p17，如图表示中设置不可达为无穷大一样，循环条件就只需要让k从low到high；第二个为练习2.3-2（p22）修改为不带哨兵的merge，循环条件改为i和j都小于各自长度，不过存在某个数组没有归并完成的可能，所以需要增加2个判断，将剩下的继续归并到v。
测试结果蛮符合理论的
当然，还有个，是可以在merge过程中，使用插入排序。尽管归并排序最坏情况运行时间仍为O(nlgn)，插入排序最坏情况下运行时间为O(n2)，但插入排序中的常数因子可以让它在n较小时，运行得更快一些。因为，在归并中，当子问题足够小时，差用插入排序就比较适合了。对n/k个长度为k的子数组进行排序，再标准合并，不过k的值怎么取是个问题。
最后还提到个shell排序，其实也是一种插入排序，只是对序列的周期子序列采用插入排序。实现如下：
void ShellInsert(vector<int> &v , int dk)
{//对v做一趟shell插入排序，增量为dk，不是1；j<=0时，找到插入位置
int i,j;
for ( i=dk ; i < v.size() ; i++)
{
if (v[i] < v[i-dk])
{
int temp = v[i];//暂存
for (j=i-dk ; j>0 && temp < v[j] ; j -= dk)
v[j+dk] = v[j] ;//记录后移，查找插入位置
v[j+dk] = temp; //插入
}
}
}
void ShellSort(vector<int> &v ,const int dlta[] ,int t)
{//希尔排序
for (int k=0 ; k < t ; k++)
ShellInsert(v,dlta[k]) ;//一趟增量为dlta[k]的插入排序
}
另外，最蛋疼的冒泡排序，也可以改为双向，分别向大和小端冒泡，虽然实际上速度并没有提升，实现如下：
for (i=0 ; i< MAX ; i++)
{
int k = MAX - i - 1;
for (j=i+1 ; j< k ; j++)
{
if (v1[j] < v1[i])
{
swap(v1[i],v1[j]);
}
if (v1[MAX-j-1] < v1[k])
{
swap(v1[MAX-j-1],v1[k]);
}
}
}在MAX=9000时，以上所有算法运行时间（win7+vc6）
insert cost : 1828
binary insert cost : 1210
reverse cost : 1193
merge cost : 91 （以前没觉得分治哥这么给力）
bubble cost : 4366
two way bubble cost : 4121
gcc下为：
insert cost : 283
binary insert cost : 224
reverse cost : 192
merge cost : 29
bubble cost : 686
two way bubble cost : 631
第三章
主要是几个渐进上下界的定义，如图
第四章
主要讲递归式，以及三种求解方式：代换法，递归树方法，主方法。感觉数学的东西居多，没有细看。不过递归的写法，简洁性还是可以的，效率未知，不过参考插入的递归，还是很可观的。最快的快排不也是递归呢么？
递归，果然是高级货啊，突然想到递归插入会溢出，而递归的快排则不会。莫非是收敛速率的问题？快排以一半的速度减少，而插入，则以相同数量级减少。
第五章
主要围绕一个雇佣问题展开，问题：有一批参与面试的人，你要一个个面试(面试每个人都要花费c1)，如果当前面试者比自己的助理能力强，则辞掉当前助理的，并把当前面试者提拔为助理(雇佣一个人要花费c2)，一直面试完所有人。
另一个很有意思的是“生日悖论”P62。问题：一个房间里的人达到多少，才能使有2个人生日相同的机会达到50%。答案居然是23，确实蛮震撼的。
很重要的2个东东，概率分析，随机算法。
随机算法，很重要的一点，是随机性发生在算法上，而不是发生在输入分布上。大多数编程环境提供伪随机数生成器。比如C/C++库函数rand()不过它并不是真正意义上的随机函数，所以称之为伪随机函数。因为当srand(seed)设置的seed一样时，则rand()产生的随机数也一样。 所以一般用 srand((unsigned)time(NULL))，采用当前时间作为种子来产生随机数。
另外，球与盒子，在线招聘等问题，都是概率论上的问题了。
P68还提到个概率计数法，一般用b位计数器，只能到2的b次方-1，不过用概率计数法，可以到很大的值，不过代价是精度有所损失，哎，高级货啊。
继续前进ing