首页 > 代码库 > 重复造轮子系列--插入排序和归并排序
重复造轮子系列--插入排序和归并排序
囧,道理很简单,实践起来却不容易。
因为编程语言跟算法描述数据结构并不能完全一致,所以理论到实践还是有些出入的。
下面的例子是没有哨兵位置的实现:
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <cassert> 5 6 using namespace std; 7 8 template<typename _InIt, typename _Func> 9 void insert_sort(_InIt first, _InIt last, _Func& Func) { 10 typedef typename iterator_traits<_InIt>::value_type _ValueType; 11 12 for (_InIt it = first + 1; it != last; ++it) { 13 _ValueType key = *it; 14 _InIt ite = it - 1; 15 for (; (ite - first)>=0 && Func(*ite, key); --ite) 16 *(ite + 1) = *ite; 17 *(ite + 1) = key; 18 } 19 } 20 21 template<typename _InIt, typename _Func> 22 void __merge(_InIt first, _InIt last, _Func& Func) { 23 typedef typename iterator_traits<_InIt>::value_type _ValueType; 24 vector<_ValueType> lv, rv; 25 26 // if((last-first) == 1) return; //这行代码折磨了我了好长时间,重新写了个C语言版找回自信,然后去洗了个澡回来发现了,赶紧去掉 27 size_t r = last-first; 28 size_t q = floor((r)/2); 29 30 copy(first, first+q+1, back_inserter(lv)); 31 copy(first+q+1, last+1, back_inserter(rv)); 32 33 typename vector<_ValueType>::iterator lit = lv.begin(); 34 typename vector<_ValueType>::iterator rit = rv.begin(); 35 36 for (_InIt it=first; it!=last+1; ++it) { 37 if (Func(*lit, *rit)) { 38 if (lit != lv.end()) { 39 *it = *lit; 40 lit++; 41 } 42 } else { 43 if (rit != rv.end()) { 44 *it = *rit; 45 rit++; 46 } 47 } 48 } 49 } 50 51 template<typename _InIt, typename _Func> 52 void __merge_sort(_InIt first, _InIt last, _Func& Func) { 53 if (last - first > 0) { 54 size_t q = floor((last - first)/2); 55 __merge_sort(first, first+q, Func); 56 __merge_sort(first+q+1, last, Func); 57 __merge(first, last, Func); 58 } 59 } 60 61 template<typename _InIt, typename _Func> 62 void merge_sort(_InIt first, _InIt last, _Func& Func) { 63 __merge_sort(first, last-1, Func); 64 } 65 66 template<typename T> 67 void print(const vector<T>& v) { 68 for(vector<int>::const_iterator it=v.begin(); it != v.end(); it++) 69 cout << *it << " "; 70 cout << endl; 71 } 72 73 int main() { 74 int lst[] = {1,5,2,6,3,7,4,8}; 75 vector<int> v(lst, lst+8); 76 77 less<int> l; 78 insert_sort(v.begin(), v.end(), l); 79 print(v); 80 81 int lst2[] = {2,4,5,7,1,2,3,6}; 82 vector<int> v2(lst2, lst2+8); 83 less_equal<int> lq; 84 85 merge_sort(v2.begin(), v2.end(), lq); 86 print(v2); 87 88 return 0; 89 }
重复造轮子系列--插入排序和归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。