- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <ctime>
- #include <functional>
- #include <string>
- #include <list>
- using namespace std;
- template<typename type, typename comparator = std::less<type>>
- struct mergesort{
- public:
- typename typedef std::vector<type> arraytype;
- typename typedef std::vector<type>::const_iterator constitrtype;
- typename typedef std::vector<type>::difference_type difftype;
- private:
- arraytype values;
- comparator compare;
- public:
- mergesort(){};
- mergesort(const arraytype val,const comparator& cmp = comparator())
- : values(val), compare(cmp){}
- mergesort(const type* begin, const type* end, const comparator& cmp = comparator())
- : values(begin,end), compare(cmp) {}
- arraytype doit(){ return _sortit(values.begin(), values.end()); }
- private:
- //helper function
- arraytype _sortit(constitrtype begin, constitrtype end)const{
- if(end - begin < 2) return arraytype(begin,end);
- arraytype left, right;
- difftype mid = (end-begin) / 2;
- left = _sortit(begin, begin + mid );
- right = _sortit(begin + mid , end );
- return _mergesort(left,right);
- }
- arraytype _mergesort(const arraytype& leftarray, const arraytype& rightarray)const{
- arraytype lhs(leftarray);
- arraytype rhs(rightarray);
- arraytype result;
- while(!lhs.empty() && !rhs.empty()){
- type elem = compareelem(lhs.front(),rhs.front());
- if(elem == lhs.front() ) lhs.erase(lhs.begin());
- else rhs.erase( rhs.begin() );
- result.push_back( elem );
- }
- std::copy(lhs.begin(),lhs.end(), std::back_insert_iterator<arraytype>(result) );
- std::copy(rhs.begin(),rhs.end(), std::back_insert_iterator<arraytype>(result) );
- return result;
- }
- type compareelem(const type& lhs, const type& rhs)const{
- return compare(lhs,rhs) ? lhs : rhs;
- }
- };
- template<typename input>
- void println(const input& in){
- cout << in << endl;
- }
- int main(){
- srand( static_cast<unsigned>(time(0)) );
- const int size = 7;
- int values[size] = {0};
- std::generate( values, values + size, rand );
- mergesort<int > msort(values,values+size);
- vector<int> sorted = msort.doit();
- cout <<"using std::less as comparison :\\n";
- std::for_each( sorted.begin(), sorted.end(),println<int>);
- mergesort<int, std::greater<int> > greatersort(values,values +size);
- vector<int> greatersorted = greatersort.doit();
- cout << "\\n\\nusing std::greater as comparison : \\n";
- std::for_each( greatersorted.begin(), greatersorted.end(), println<int> );
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/201120137348.html
来源: http://www.codesnippet.cn/detail/201120137348.html