看书、思考、写代码！

/***********************************************

* copyright@hustyangju

* blog: http://blog.csdn.net/hustyangju

* 2014-11-03

* 题目： 插入排序

* 描写叙述： 给定一个数组，依照逐个插入比較的方法得到一个已序数组

* 解题思路：从第一个元素開始，在已序数组上插入下一个元素，能够从已序数组的尾部。也能够从头部逐个比較插入

* 时间复杂度：原数组顺序排好的情况下，时间复杂度最好，为O（n）。原数组逆序排好时，时间复杂度最坏。为O(n^2)，平均时间复杂度为O（n^2）

* 空间复杂度：仅仅用到一个暂时变量。在原数组上排序，空间复杂度为O（1）

************************************************/

#include <iostream>

using namespace std;

template<class type>

class insert_sort

{

public:

    insert_sort(type *p,int num):_p(p),_num(num){}

    ~insert_sort();

    void sort();

    void print();

private:

    type *_p;

    int _num;

};

template<class type>

insert_sort<type>::~insert_sort()

{

}

template<class type>

void insert_sort<type>::sort()

{

    for(int i=1;i<_num;i++)

    {

        int j=i-1;

        type key=_p[i];

        while((j>=0)&&(_p[j]>key))

        {

            _p[j+1]=_p[j];

            j-=1;

        }

        _p[j+1]=key;

    }

}

template<class type>

void insert_sort<type>::print()

{

    for(int i=0;i<_num;i++)

    {

        cout<<*_p<<" ";

        _p++;

    }

     cout<<endl;

}

int main()

{

    float array[5]={5.1,3,6.8,9.1,10};

    int array1[10]={22,8,9,42,2,78,9,33,11,10};

    insert_sort<float> mysort(array,5);

    mysort.sort();

    mysort.print();

    insert_sort<int> mysort1(array1,10);

    mysort1.sort();

    mysort1.print();

    //system("PAUSE");

}