Combsort（使用G++4.8.1）

andalousie

用的是我自己的iostream，所以包含的头文件多一点。如果用标准库的iostream的话，则不需要其他头文件。

#include "ios.h"
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_iterator_base_funcs.h>
#include <bits/stl_iterator.h>
#include <bits/stl_algobase.h>

template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
    static const double shrink_factor = 1.247330950103979;
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type gap = std::distance(first, last);
    bool swaps = true;
 
    while ( (gap > 1) || (swaps == true) ){
        if (gap > 1)
            gap = static_cast<difference_type>(gap/shrink_factor);
 
        swaps = false;
        ForwardIterator itLeft(first);
        ForwardIterator itRight(first); std::advance(itRight, gap);
 
        for ( ; itRight!=last; ++itLeft, ++itRight ){
            if ( (*itRight) < (*itLeft) ){
                std::iter_swap(itLeft, itRight);
                swaps = true;
            }
        }
    }
}

template<typename T, std::size_t n>
 T* end(T (&array)[n])
{
  return array+n;
}
 
int main() {
    int myints[] = {249, 2423, 232, 21, 1637, 35, 2556, 257};
        combsort(myints, end(myints));
        std::cout << "Sorted list/array: ";
        for(unsigned int i=0; i<8; i++)
                std::cout << myints[i] << ' ';
}