算法导论习题（持续更新）

算法导论 华章第三版 习题
##练习题2.1-2
重写过程INSERTION-SORT，使之按非升序排序。
伪代码思路1：

for j=A.length-1 to 1key=A[j]i=j+1while i<A.length+1 and A[i]>kA[i-1]=A[i]i=i+1A[i-1]=key

所有排好序的序列都放在数组A的右边，从右到左遍历整个A，将其插入到右面有序的序列中
伪代码思路2：
所有排好序的序列仍然都放在数组A的左边，

for j=2 to A.lengthkey=A[j]i=j-1while i>0 and A[i]<keyA[i+1]=A[i]i=i-1A[i+1]=key

##练习题2.1-3
考虑以下查找问题：
输入：n个数的一个序列A=<a1,a2,…,an>和一个值v。
输出：下标i使得v=A[i]或者当v不在A中出现时，v为特殊值NIL。
写出线性查找的伪代码，它扫描整个序列来查找v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。

for i=1 to A.lengthif A[i]==vreturn i
return NIL

##练习题2.1-4
考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个（n+1）元数组C中。请给出该问题的形式化描述，并写出伪代码。

for i=1 to nval =A[i]+B[i]if val==0C[i]+=0else if val==1C[i]+=1else if val==2C[i]+=0C[i+1]+=1else if val==3C[i]+=1C[i+1]+=1

##练习题2.2-2
考虑排序存储在数组A中的n个数：首先找出A中的最小元素并将其与A[1]中的元素进行交换。接着，找出A种的次最小元素并将其与A[2]中的元素进行交换。对A中前n-1个元素按该方式继续。该算法成为选择算法，写出其伪代码。该算法维持的循环不变式是什么？为什么它只需要对前n-1个元素，而不是对所有n个元素运行，用theta记号给出选择排序的最好情况与最坏情况运行时间。

min=+inv
for i=1 to n-1for j=i to n-1if A[j]<minmin=A[j]j_min=jexchange=A[i]A[i]=A[j_min]A[j_min]=exchange

theta(n方)？？？