习题是自己思考之后做的，如有错误欢迎指正和交流

2.1-1

2.1-1
注意步骤d，只会发生一次轮换，而不是两次

2.1-2

INSERTION-SORT(A)
  for j=2 to A.length
    key = A[j]
    //insert A[j] into the non-ascending sequence
    i = j - 1
    while i > 0 and A[i] < key
      A[i+1]=A[i]
      i = i - 1
    A[i + 1] = key

2.1-3

伪代码

MYSEARCH(A, v)
    for i = 1 to A.length
       if A[i] == v
            return i
    return NIL

循环不变式

• 初始化： 第一次循环(i=1)开始之前，i=0时，A[0]不存在，所以直接进入return NIL，为真
• 保持： 如果会进入下一个循环i，代表A[0]到A[i-1]都不等于v，所以此时，没有return，是正确的
• 终止： 当A[i]等于v时，返回i。如果检查完A的每个元素后，都不等于v，返回空，正确

2.1-4

输入： 两个n位的二进制整数A和B
输出： 相加之后的二进制整数C

MY-ADD(A, B)
  C[1] = 0
  for i = 1 to n
    C[i] = (A[i] + B[i] + C[i]) % 2
    C[i+1] = (A[i] + B[i] + C[i]) / 2
  return C