算法导论 — 2.1 插入排序

笔记

插入排序是最简单的一种排序算法，它的伪代码如下。
　　
　　相信读者对插入排序都很熟悉，并且算法很简单，这里就不做具体分析了。

练习

2.1-1 以图2-2为模型，说明INSERTION-SORT在数组$A = &lt;31, 41, 59, 26, 41, 58&gt;$A=<31,41,59,26,41,58>上的执行过程。
　　解
　　
　　
2.1-2 重写过程INSERTION-SORT，使之按非升序（而不是非降序）排序。
　　解
　　
　　
2.1-3 考虑以下查找问题：
　　输入：$n$n个数的一个序列$A = &lt;a_1, a_2, …, a_n&gt;$A=<a1​,a2​,…,an​>和一个值$v$v。
　　输出：下标$i$i使得$v = A[i]$v=A[i]或者当$v$v不在$A$A中出现时，$v$v为特殊值${\rm NIL}$NIL。
　　写出线性查找的伪代码，它扫描整个序列来查找$v$v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。
　　解
　　
　　
2.1-4 考虑把两个$n$n位二进制整数加起来的问题，这两个整数分别存储在两个$n$n元数组$A$A和$B$B中。这两个整数的和应按二进制形式存储在一个$(n+1)$(n+1)元数组$C$C中。请给出该问题的形式化描述，并写出伪代码。
　　解
　　
　　
　　本节代码链接：https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter02/Section_2.1