看書、思考、寫代碼！

/*********************************************** * 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"); }

總結

以上是生活随笔為你收集整理的《github一天一道算法题》：插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。