插入算法，貪心算法

插入算法，貪心算法

插入學習算法是一種原地排序（sorted in place）的算法，亦即不用重新分配內存，在原數組或者vector中進行排序的。

其偽代碼為

#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<<"\t";
        ++it;
    }
    
}