一、插入排序：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中，請給出這個問題的形式化描述，并寫出僞代碼。。
解答：