一、插入排序：INSERTION-SORT
1、适用范围：
which is an efficient algorithm for sorting a small number of elements.
对于少量元素的排序，插入排序是一种高效的算法。
2、原理：
Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table.
We then remove one card at a time from the table and insert it into the correct position in the left hand.
To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left,
插入排序原理和玩纸牌一样，我们原本左手中没有牌，牌都在桌子上放着，我们从桌子上取出一张牌，并插入到左手中。
第一次插入为直接插入，因为此时我们手中没牌，等到第二次插入时，我们和第一次插入的牌比较，将大的放在右边，小的放在左边。
第三次插入则是将从桌子上取的牌，和手中的每一张牌以从右往左的顺序比较，将牌插入到合适的位置。
3、插入排序伪代码：
说明：j代表索引，此处索引从1开始，而非0，插入时从第二个数字开始插入；
循环不变式（上述插入排序的不变式为A[1..j-1]）：用于帮助理解算法正确性，必须证明其三个性质：
2.1-1 以图2-2模型为例，说明插入排序在数组A=[31,41,59,26,41,58]上的执行过程。
2.1-2 重写Insert-sort，使之按照非升序（而非非降序）排序
INSERT_SORT (A)
2.1-3 考虑下面的查找问题
输入：一列数A=(a, a2,..., an)和一个值v。
输出：下标i，使得v=A[i]，或者当v不在A中出现时为NIL。
写出针对这个问题的线性查找的伪代码，它顺序的扫描整个序列以查找v，利用循环不变式证明算法的正确性。确保所给出的循环不变式满足三个必要的性质。
伪代码（可能不符合标准，但基本意思表达）：
2.1.4
有两个各存放数组A和B的n位二进制数，考虑他们的相加问题，两个整数的和以二进制形式存放在具有n+1个元素的数组C中，请给出这个问题的形式化描述，并写出伪代码。。
解答：