首页 > 代码库 > 《github一天一道算法题》:插入排序
《github一天一道算法题》:插入排序
看书、思考、写代码!
/*********************************************** * 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一天一道算法题》:插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。