插入排序的基本介绍

对于少量元素的排序，它是一个有效的算法。
你可以把它想象初始手牌为空，然后从牌堆里依次抽取一张牌，并从左到右依次与手上的牌进行比较，直到找到合适的位置。
对于实际程序来说，则是从给定序列中获取到一个元素，然后与现在序列中已有的数进行依次比较，然后在正确的位置插入当前元素。

插入排序有效性的证明

循环不变式的引入

初始化：循环的第一次迭代之前，它为真。
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。
用人说的话解释一下就是：
一个正确的算法在循环过程中总是维持一个不变的特性，这个特性一直保持到循环结束甚至算法结束，这样就可以保证算法的正确了。
例如对于插入排序保证的特性就是前n个数永远的有序的，因为到算法结束为止，这个特性一直保持存在，于是可以说明当前算法的正确性。

练习

2.1.1以图2.2为模型，说明INSERTION-SORT在数组A<31,41,59,26,41,58>上的执行过程。
第一趟：
A<31,41,59,26,41,58>
第二趟
A<31,41,59,26,41,58>
第三趟
A<26,31,41,59,41,58>
第四趟
A<26,31,41,41,59,58>
第五趟
A<26,31,41,41,58,59>

2.1.2重写过程INSERTION-SORT，使之按非升序(而不是非降序)排序。
原始数组：
A<5,2,4,6,1,3>
第一趟：
A<5,2,4,6,1,3>
第二趟
A<5,4,2,6,1,3>
第三趟
A<6,5,4,2,1,3>
第四趟
A<6,5,4,2,1,3>
第五趟
A<6,5,4,3,2,1>

2.1.3考虑以下查找问题：
输入：n个数的一个序列A=和一个值v。
输出：下标i使得v=A[i]或者当v不在A中出现时，v为特殊值NIL。
写出线性查找的伪代码，它扫描整个序列来查找v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。

#include<iostream>
using namespace std;
int main()
{
    int A[100];
    int n,i,v;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>A[i];
    }
    cin>>v;
    for(i=0;i<n;i++)
    {
        if(A[i]==v)
        {
            cout<<i+1<<endl;
            return 0;
        }
    }
    cout<<"NIL"<<endl;
    return 0;
}

初始化：在第一次循环迭代之前，i=0，i保持：在循环达到条件A[i]==v时，循环条件一直成立，在下次迭代之前循环条件依然为真。
终止：在循环达到终止时，A[i]==v或者i>=n，我们得到了需要的第i个数等于v，或者没有任何一个数等于v。

2.1.4考虑把两个n位二进制整数加起来的问题，这两个整数分别存储在两个n元数组A和B中。这两个整数的和应该按二进制形式存储在一个(n+1)元数组C中。请给出该问题的形式化描述，并写出伪代码。

#include<iostream>
using namespace std;
int main()
{
    int A[100];
    int B[100];
    int C[100];
    int n,i;
    int upflag=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>A[i];
    }
    for(i=0;i<n;i++)
    {
        cin>>B[i];
    }
    for(i=n-1;i>=0;i--)
    {
        if(i==0)
        {
            C[1]=(A[0]+B[0]+upflag)%2;
            C[0]=(A[0]+B[0]+upflag)/2;
        }
        else
        {
            C[i+1]=(A[i]+B[i]+upflag)%2;
            upflag=(A[i]+B[i]+upflag)/2;
        }
    }
    for(i=0;i<n+1;i++)
    {
        cout<<C[i];
    }
    cout<<endl;
    return 0;
}