2-3-1：
2-3-2：
MERGE2(A,p,q,r)
n1=q-p+1
n2=r-q
let L[1..n1]and R[1...n2] be new arrays
for i=1 to n1
L[i]=A[p+i-1]
for j=1 to n2
R[j]=A[q+j]
i=1
j=1
k=1
while i<=n1 and j<=n2
if L[i]<=R[j]
A[k]=L[i]
i=i+1
else
A[k]=R[j]
j=j+1
k=k+1
while i>n1 and j<=n2
A[k]=R[j]
k=k+1
j=j+1
while i<=n1 and j>n2
A[k]=L[i]
k=k+1
i=i+1
2-3-4：
//此处输入为A[1...n] RECURSIVE-INSERTON-SORT(A,n) if n>1 RECURSIVE-INSERTION-SORT(A,n-1) key=A[n] i=n-1 while i>0 and A[i]>key A[i+1]=A[i] i=i-1 A[i+1]=key
上述的递归版本与迭代版本的思想基本一致
T(n) = theta(1) n=1 or 2
=T(n-1)+theta(n) n>2
2-3-5:
//以下是二分查找的两个版本，递归版本和迭代版本 //参数是A[low..high]以及要查找的值v ITERACTIVE-BINARY-SEARCH(A,v,low,high) while low<=high mid=floor((low+high)/2) if v==A[mid] return mid else if v>A[mid] low=mid else high=mid return NIL RECURSIVE-BINARY-SEARCH(A,v,low,high) if low>high return NIL mid=floor((low+high)/2) if v==mid return mid else if v>A[mid] return RECURSIVE-BINARY-SEARCH(A,v,mid,high) else return RECURSIVE-BINARY-SEARCH(A,v,low,mid)
c++实现（迭代版）：
//要求T是可比较的
template<typename T>
int binary_search(T* A,T v,int low,int high)
{
int mid=0;//计算中值，初始化；
/*这里的条件是：high-low至少大于1，如果条件是low<=high的话，可能是个死循环
*例如A[5]={0,1,2,3,4,5} 查找3.5
*/
while(high-low>1){
mid=(low+high)/2;
if(v==A[mid])
return mid;
else if(v>A[mid])
low=mid;
else
high=mid;
}
return -1;//表示没有找到
}
根据递归版本，写出递归式：
T(n)=T(n/2)+theta(1)画递归树求得，T(n)=theta(lgn)
2-3-6：
不能。因为对于查找位置，比较大小，固然可以在lgj时间内找到，但是对于移动复制元素的时间却是j
2-3-7：
这个嘛，排序theta（nlgn），然后对于每一个元素i：1 to n，令y=x-S[i]，然后在S[1..n]上二分查找y，总共也是theta（nlgn）。所以总的为theta（nlgn）
不过http://www.cnblogs.com/liao-xiao-chao/articles/2351925.html
这里有个更好的方法
思考题：
2-1：
伪代码：
MERGR-SORT(A,p,r)
if (r-p)>k
q=floor( (p+r)/2)
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,r)
else
INSERTION-SORT(A,p,r)
此处使用的INSERTION-SORT，不同于前面使用的INSERTION-SORT，因为此处参数发生改变：
const int k=5;//此处k取5
template<typename T>
void insertion_sort(T* A,int low,int high)
{
int key=0;//key初始化
for(int j=low+1;j<=high;++j){
//进行A[j]的插入工作
key=A[j];
int i=j-1;
while(i>=low && A[i]>key){
A[i+1]=A[i];
i=i-1;
}
A[i+1]=key;
}
}
void merge_sort(int* A,int p,int r)
{
if(r-p>=5){
int q=(p+r)/2;
merge_sort(A,p,q);
merge_sort(A,q+1,r);
merge(A,p,q,r);
}else{
insertion_sort(A,p,r);
}
}
merge(A,p,q,r)的具体代码见前一篇《归并排序》。
a.证明：插入排序的复杂度为theta(n^2)，设T(n)=cn^2，当长度为k时，T(k)=ck^2;总共有n/k段，所以T(n)'=（n/k)*(ck^2)=c*nk,所以复杂度为theta(nk);
b.证明: 此时，最底层总共n/k段，总共多少层呢？2^h*k=n => h=log(n/k) 每一层的合并都是theta(n),所以，合并的总时间复杂度为theta(nlg(n/k));
c.T(n)=对最后n/k段插入排序的时间+总的合并时间=theta(nk+nlog(n/k))
d.当输入好的情况多的时候，k取较大值；当输入差的情况多时，k取较小值（这个答案是摘抄的。。。）
2-2：（冒泡排序）：
伪码：
BUBBLE-SORT(A)
for i= 1 to A.length-1
for j=A.length downto i+1
if A[j]<A[j-1]
exchange A[j] with A[j-1]
a.我觉得可能是：A'[1..n]中的元素由A[1..n]中的元素构成
b.2-4行的循环不变式：每次循环开始时，A[j]中的元素是A[j...A.length]中最小的元素
证明：
初始化。j=A.length。此时正确；
保持：
终止：j=i时终止。此时A[i]是A[i...A.length]中最小的元素；
c.1-4行的循环不变式：每次循环开始时，A[1..i-1]中的元素是A[1..n]中前i-1个最小的元素，且A[1..i-1]已序。
证明：
初始化：i=1；成立
保持：对于i，2-4行保证最后A[i]是A[i..A.length]的最小元素；
终止：i=A.length.A[1...A.length-1]已序，且都小于A[A.length]，所以最后排序算法正确；
d.theta(n^2)
2-3（霍纳规则）：
求解：
y=0
for i=n downto 0
y=ai+x*y
a.theta(n)
b.朴素多项式求值：
y=a0
for i= 1 to n
xi=1
for j=0 to i
xi=xi*x
y=y+ai*xi
运行时间为theta(n^2)，性能远不如霍纳规则
c.当终止时，i=-1；此时带入，则得出结论
c++代码：
//参数A[0...n-1]，n为长度，coef为参数数组，x为未知数
template<typename T>
T Horner(T* coef,T x,int n)
{
T y=T(0);
for(int i=n-1;i>=0;--i){
y=coef[i]+x*y;
}
return y;
}
2-4（逆序对）：
a.
i: 1 2 3 4 5
A:< 2 3 8 6 1>
当i=1时，寻找j>1且A[j]<A[i] 得j=5，<1,5>
当i=2时，寻找j>2 and A[j]<A[2] j=5 <2,5>
i=3 , j>3 and A[j]<a[3] j=4,5 <3,4><3,5>
i=4 j>4 and A[j]<A[4] j=5 <4,5>
b.数组元素降序排列，有n*(n-1)/2个逆序对
c.所谓逆序对，就是对于A[j]，寻找A[1...j-1]中小于A[j]的元素，若A[1...j-1]已升序排列，则，这就是插入排序的插入过程，所以说，逆序对越多，插入排序越慢；插入排序就是消除逆序对的过程；
d.伪码：
//改编归并排序即可，左数组中的逆序对，加上右数组
//中的逆序对，再加上右数组对左数组的逆序对即可
COUNT-INVERSION(A,p,r)
inversions=0
if p<r
q=floor( (p+r)/2)
inversions=inversions+COUNT-INVERSION(A,p,q)
inversions=inversions+COUNT-INVERSION(A,q+1,r)
inversions=inversions+MERGE-INVERSION(A,p,q,r)
return inversions
MERGE-INVERSION(A,p,q,r)
n1=q-p+1
n2=r-q
let L[1...n1+1] and R[1..n2+1] be new arrays
for i=1 to n1
L[i]=A[p+i-1]
for j= 1 to n2
R[j]=A[q+j]
L[n1+1]=INF
R[n2+1]=INF
i=1
j=1
inversions=0
for k=p to r
if L[i]>R[j]
inversions=inversions+n1-i+1//注意此处如果c++实现的话，inversions+=n1-i;因为c++从0开始
A[k]=R[j]
j=j+1
else if L[i]<=R[j]
A[k]=L[i]
i=i+1
return inversions
此处只需将归并排序稍加改动即可，就不上传c++代码了。