《算法导论》（第二版）【2.1】笔记及习题解答
2.1 插入排序
概念
插入排序算法
本算法要解决的是排序问题：
输入：n个数<a1,a2,…,an>。
输出：输入序列的一个排列（即重新排序）<a\’1,a\’2,…,a\’n>，使得a\’1≤a\’2≤…≤a\’n。
待排序的数也称关键字（key）。
以下插入排序算法的伪代码以一个过程的形式给出，称为INSERTION-SORT，它的参数是一个数组A[1..n]，包含了n个待排序的数。A中元素的个数n用length[A]表示。输入的各个数字是原地排序的（sorted in place），意即这些数字就是在数组A中进行重新排序的，在任何时刻，至多只有其中的常数个数字是存储在数组之外的。当过程INSERTION-SORT执行完毕后，输入数组A中就包含了已排好序的输出序列。
INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do key ← A[j]
3 ▷ Insert A[j] into the sorted sequence a[1..j-1]
4 i ← j – 1
5 while i>0 and A[i]>key
6 do A[i+1] ← A[i]
7 i ← i – 1
8 A[i+1] ← key
在上述伪代码中，外层for循环的每一轮迭代开始，包含元素A[1..j-1]子数组是一个已经排好序的数组，内部while循环要做的就是将A[j-1]，A[j-2]A[j-3]等元素依次向右移动一个位置，直到A[j]找到适当的位置为止。
循环不变式
循环不变式主要用来帮助我们理解算法的正确性，对于循环不变式，必须证明它的三个性质：
初始化：它在循环的第一轮迭代开始之前，应该是正确的。
保持：如果在循环的某一次迭代开始前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确。
终止：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。
伪代码中的约定
1）用“缩进”表示程序中的分程序（程序块）结构。
2）while ,for, repeat等循环结构，和if, then, else条件结构与Pascal中相同。for循环后循环计数器的值仍然保持。
3）符号“▷”表示后面不是是个注释。
4）多重赋值i←j←e是将表达式e的值赋给变量i和j。
5）变量是局部于给定过程的。没有显示说明的情况下，不使用全局变量。
6）数组元素通过“数组名[下标]”的形式访问。符号“..”表示数组的一个取值范围，例如A[2..j]包含了j-1个元素A[2]，A[3]，…，A[j]。
7）复合数据一般组织成对象，它们由属性（attribute）或域（filed）所组成。域的访问时有域名后跟由方括号括住的对象名形式表示。如，数组可被看作一个对象，其属性有length，length[A]就表示数组中的元素个数。用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f，赋值y←x就使得f[y]=f[x]。在赋值y←x后，x和y指向同一个对象。
8）参数采用按值传递方式：被调用的过程会收到参数的一份副本。如果它对某个参数赋值的话，主调过程是看不见这一变动的。当对象被传递时，实际传递的是一个指向该对象数据的一个指针，而对象的各个域则不被拷贝。
9）布尔运算符and和or都有短路能力。意即，当求表达式“x and y”的值时，先计算x的值。如果x的值为FALSE，那么整个表达式的值就不可能为TRUE，就无需对y求值。短路运算符允许我们写出如“x≠NIL and f[x]=y”这样的表达式，而不用担心当我们试图在x为NIL时计算f[x]，会发生怎样的情况。
10）【个人额外补充】数组下标通常从1开始而非0。”=”是逻辑运算符，赋值符号是“←”。
习题解答
2.1-1 以图2-2为模型，说明INSERTION-SORT在数组A=<31, 41, 59, 26, 41, 58>上的执行过程。
31 【(41)】 59 26 41 58
31 41 【(59)】 26 41 58
（） 31 41 59 【26】 41 58
26 31 41 （） 59 【41】 58
26 31 41 41 （） 59 【58】
26 31 41 41 58 59
2.1-2 重写过程INSERTION-SORT，使之按非升序排序。
INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do key ← A[j]
3 ▷ Insert A[j] into the sorted sequence a[1..j-1]
4 i ← j – 1
5 while i>0 and A[i]<key
6 do A[i+1] ← A[i]
7 i ← i – 1
8 A[i+1] ← key
将原代码第五行大于改为小于即可
2.1-3 考虑下面的查找问题：
输入：一列数A=<a1,a2,…,an>和一个值v。
输出：下标i，是的v=A[i]，或者当v不在A中出现时为NIL。
写出针对这个问题的线性查找的伪代码，它顺序地扫描整个序列以查找v。利用循环不变式正面算法的正确性。确保所给出的循环不变式满足三个必要的性质。
LINEAR-SEARCH(A, v)
for i ← 1 to length[A]
do if A[i] = v
do return i
return NIL
初始化：初始化i为1，从数组第一个元素开始查找。
保持：每次迭代，下标增长1，顺序查找数组，满足条件return当前下标结束循环，或者遍历完数组结束循环
终止：两个return语句，一个在循环体中，找到复合条件的下标直接返回，终止循环；一个是循环计数器i达到length[A]+1以后结束，说明没有找到复合条件的A[i]，v不在A中，正确返回NIL。
2.1-4 有两个各存放在数组A和B中的n位二进整数，考虑他们的相加问题。两个整数的和以二进制形式存放在具有（n+1）个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。
输入：存放两个二进制数a1a2…an和b1b2…bn的数组A=<a1,a2,…,an>和B=<b1,b2,…,bn>
输出：数组C=<c1,c2,…,cn>使得二进制数c1c2…cn=a1a2…an+b1b2…bn
伪代码：
Binary-ADD(A,B)
creat arrays C[0..0n+1]
carry ← 0
for i ← n to 1
do v ← A[i]+B[i]+carry
if v > 1
do carry ← 1
C[i+1] ← v-2
else
do carry ← 0
C[i+1] ← v
C[1] ← carry
return C