笔记
插入排序是最简单的一种排序算法，它的伪代码如下：
代码2.1-1：插入排序
// 参数 A：待排序的数组
INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
// Insert A[j] into the sorted sequence A[1..j-1]
i = j-1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i-1
A[i+1] = key
练习
2.1-1 以图2-2为模型，说明INSERTION-SORT在数组上的执行过程。
解
2.1-2 重写过程INSERTION-SORT，使之按非升序（而不是非降序）排序。
解
代码2.1-2：非升序插入排序
// 参数 A：待排序的数组
REVERSE-INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
// Insert A[j] into the sorted sequence A[1..j-1]
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 考虑以下查找问题：
输入：个数的一个序列
和一个值
。
输出：下标使得
或者当
不在
中出现时，
为特殊值
。
写出线性查找的伪代码，它扫描整个序列来查找。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。
解
代码2.1-3：线性查找
// 参数 A：一个数组
// 参数 v：需要查找的值
LINEAR-SEARCH(A, v)
for i = 1 to A.length
if A[i] == v
return i
return NIL
2.1-4 考虑把两个位二进制整数加起来的问题，这两个整数分别存储在两个
元数组
和
中。这两个整数的和应按二进制形式存储在一个
元数组
中。请给出该问题的形式化描述，并写出伪代码。
解
代码2.1-4：二进制整数相加
// 参数 A和B：表示两个二进制整数的数组，数组中的元素只能是0或1
// 参数 n：输入数组的长度
// 参数 v：需要查找的值
BINARY-ADD(A, B, n)
create a new array C[1..n+1]
carry = 0
for i = 1 to n
sum = A[i] + B[i] + carry
if sum < 2
C[i] = sum
carry = 0
else
C[i] = sum - 2
carry = 1
C[n+1] = carry
代码链接：
https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter02/Section_2.1
