泛型插入排序

#pragma once

#include <iterator>

#include <functional>

template<

class bidirectional_iterator,

template<class> class greater_compare = std::greater

>

class insertion_sort_functor

{

public:

bool operator()(bidirectional_iterator first, bidirectional_iterator last)const

{

typedef bidirectional_iterator::value_type value_type;

typedef greater_compare<value_type> gc;

gc gc_comparer;

bidirectional_iterator j = next_iterator(first);

for( ; j!=last ; ++j)

{

value_type key = *j;

bidirectional_iterator i = last_iterator(j);

while(std::distance(first,i)>0 && gc_comparer(*i,key) )

{

*next_iterator(i) = *i;

--i;

}

if(i == first && gc_comparer(*i,key))

{

*next_iterator(i) = *i;

*i = key;

continue;

}

*next_iterator(i)= key;

}

return true;

}

private:

bidirectional_iterator last_iterator(const bidirectional_iterator& i)const

{

bidirectional_iterator j(i);

return --j;

}

bidirectional_iterator next_iterator(const bidirectional_iterator& i)const

{

bidirectional_iterator j(i);

return ++j;

}

};

测试程序

int a[]={345,67,56,6,4567467,65768,7686,-34635,67,57678,-235};

vector<int> vi(a,a+sizeof(a)/sizeof(int));

list<int> li(a,a+sizeof(a)/sizeof(int));

insertion_sort(a ,sizeof(a)/sizeof(int));

insertion_sort_functor<vector<int>::iterator, std::less>()

(vi.begin(), vi.end());

insertion_sort_functor<list<int>::iterator, std::greater>()

(li.begin(), li.end());