• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

c++实现合并排序算法

OC/C/C++ 水墨上仙 2869次浏览

c++实现合并排序算法


#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;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明c++实现合并排序算法
喜欢 (0)
加载中……