算法导论 — 2.1插入排序

笔记

插入排序是最简单的一种排序算法，它的伪代码如下：

　　代码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