插入算法

插入学习算法是一种原地排序（sorted in place）的算法，亦即不用重新分配内存，在原数组或者vector中进行排序的。

其伪代码为

1. INSERTION-SORT(A)
   for j<-2 to length[A]
        do key<-A[j]
        //INSERT A[j] into the sorted sequence A[1..j-1]
        i<-j-1
        while i>0 and A[i]>key
            do A[i+1]<-A[i]
                  i<-i-1
               A[i+1]<-key

   
   伪代码的好处在于看起来方便直观，而且在使用其他语言实现的时候也非常简单，是个非常好的表达自己思维的一种方式。

2. 使用 数组的方式实现上述伪代码

#define SIZE 6

//插入算法的数组引用实现方式
void insertion_sort(int (&array)[ SIZE])
{
    int key;
    for(int j=1;j<SIZE;j++)
    {
        key=array[j];
        int i=j-1;
        while(i>=0&&array[i]>key)
        {
            array[i+1]=array[i];
            --i;
        }
        array[i+1]=key;
    }

   其中数组的引用作为形参的时候，必须固定数组大小，可以采用#define的形式。

3.采用vector的方式进行传参

void insert_sort(vector<int>&array) //当使用vector<int>array作为形参的时候，
                                                     //不能改变原vector中对象的内容，{                                    //当使用容器的引用的时候，可以正常改变
    //利用vector下标形式进行索引，同字符串和数组
    int key;
    for(int j=1;j<array.size();j++) 
    {                                
        key=array[j];
        int i=j-1;
        while(i>=0&&array[i]>key)
        {
            array[i+1]=array[i];
            --i;
        }
        array[i+1]=key;
    }


}

这里面有个不匹配的，就是array.size()是unsigned int形式的，但是j是int类型的，两者比较的时候容易出现问题。如果将i,j定义为unsigned类型的话，while循环中，i=0的时候，--i,为无符号类型，所以i变成了2³²，于是array[i]就会溢出。如果一定要用unsigned int i,j的话，那么在主函数中要设置一个岗哨。岗哨设置在下面可以看到。

4.采用迭代器

void insertSort(vector<int>&array)
{
    vector<int>::iterator it=array.begin()+1;
    for(it+=1;it!=array.end();++it)
    {
        int key=*it;
        vector<int>::iterator ita=it-1;
        while(ita>=array.begin()+1&&(*ita)>key)
        {
            *(ita+1)=*ita;
            --ita;
        }
        *(ita+1)=key;
    }
}

int main()
{
    vector<int> A;
    A.push_back(INT_MIN);   //通过设置岗哨，可以让程序继续运行下去。
    A.push_back(5);
    A.push_back(2);
    A.push_back(4);
    A.push_back(3);
    A.push_back(1);
    A.push_back(6);
    //insert_sort(A);
    insertSort(A);
    vector<int>::iterator it=A.begin()+1;
    while(it!=A.end())
    {
        cout<<*it<<"	";
        ++it;
    }
    
}