算法导论第三版--插入排序和归并排序

囧，道理很简单，实践起来却没那么简单。因为编程语言的语言元素跟算法描述数据结构并不完全一致。

经过迭代（此处省略800字），补充上对于归并排序对于小数组采用插入排序的代码。

首先是插入排序：

 1 template<typename _InIt, typename _Func>
 2 void __insert_sort(_InIt first, _InIt last, _Func& Func) {
 3     typedef typename iterator_traits<_InIt>::value_type _ValueType;
 4 
 5     for (_InIt it = first + 1; it != last+1; ++it) {
 6         _ValueType key = *it;
 7         _InIt ite = it - 1;
 8         for (; (ite - first)>=0 && !Func(*ite, key); --ite)
 9             *(ite + 1) = *ite;
10         *(ite + 1) = key;
11     }
12 }
13 
14 template<typename _InIt, typename _Func>
15 void insert_sort(_InIt first, _InIt last, _Func& Func) {
16     __insert_sort(first, last-1, Func);
17 }

然后是普通的归并排序：

 1 template<typename _InIt, typename _Func>
 2 void __merge(_InIt first, _InIt last, _Func& Func) {
 3     typedef typename iterator_traits<_InIt>::value_type _ValueType;
 4     vector<_ValueType> lv, rv;
 5     size_t q = floor((last-first)/2);
 6 
 7     copy(first, first+q+1, back_inserter(lv));
 8     copy(first+q+1, last+1, back_inserter(rv));
 9 
10     typename vector<_ValueType>::iterator lit = lv.begin();
11     typename vector<_ValueType>::iterator rit = rv.begin();
12 
13     _InIt it = first;
14     for (; it != last+1; ++it) {
15         if (lit == lv.end() || rit == rv.end()) break;
16         *it = Func(*lit, *rit) ? *(lit++) : *(rit++);
17     }
18 
19     for(; lit != lv.end() && it != last+1; ++lit, ++it) *it = *lit;
20     for(; rit != rv.end() && it != last+1; ++rit, ++it) *it = *rit;
21 }
22 
23 template<typename _InIt, typename _Func>
24 void __merge_sort(_InIt first, _InIt last, _Func& Func) {
25     if (last - first > 0) {
26         size_t q = floor((last - first)/2);
27         __merge_sort(first, first+q, Func);
28         __merge_sort(first+q+1, last, Func);
29         __merge(first, last, Func);
30     }
31 }
32 
33 template<typename _InIt, typename _Func>
34 void merge_sort(_InIt first, _InIt last, _Func& Func) {
35     __merge_sort(first, last-1, Func);
36 }

归并排序中的小数组采用插入排序：

 1 template<typename _InIt, typename _Func>
 2 void __merge_sort(_InIt first, _InIt last, int k, _Func& Func) {
 3     if (last - first > 0) {
 4         int q = floor((last - first)/2);
 5         if (q <= k) {
 6             __insert_sort(first, last, Func);
 7         } else {
 8             __merge_sort(first, first+q, k, Func);
 9             __merge_sort(first+q+1, last, k, Func);
10             __merge(first, last, Func);
11         }
12     }
13 }
14 
15 template<typename _InIt, typename _Func>
16 void merge_sort(_InIt first, _InIt last, int k, _Func& Func) {
17     __merge_sort(first, last-1, k, Func);
18 }

测试函数：

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <cassert>
 5 
 6 using namespace std;
 7 
 8 template<typename T>
 9 void print(const vector<T>& v) {
10     for(vector<int>::const_iterator it=v.begin(); it != v.end(); it++)
11            cout << *it << " ";
12         cout << endl;
13 }
14 
15 template<typename _InIt>
16 void print(_InIt first, _InIt last) {
17     for(vector<int>::const_iterator it=first; it != last; it++)
18         cout << *it << " ";
19     cout << endl;
20 }
21 
22 int main() {
23     int lst[] = {1,5,2,6,3,7,4,8};
24     vector<int> v(lst, lst+8);
25 
26     less<int> l;
27     insert_sort(v.begin(), v.end(), l);
28     print(v);
29 
30     int lst2[] = {2,4,5,7,1,2,3,6};
31     vector<int> v2(lst2, lst2+8);
32     less_equal<int> lq;
33 
34     merge_sort(v2.begin(), v2.end(), v2.size()/2, lq);
35     //merge_sort(v2.begin(), v2.end(), lq);
36     print(v2);
37 
38     return 0;
39 }