Combsort（使用G++4.8.1）

andalousie

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

1. #include "ios.h"
   
2. #include <bits/stl_iterator_base_types.h>
   
3. #include <bits/stl_iterator_base_funcs.h>
   
4. #include <bits/stl_iterator.h>
   
5. #include <bits/stl_algobase.h>
   
6. 
   
7. template<class ForwardIterator>
   
8. void combsort ( ForwardIterator first, ForwardIterator last )
   
9. {
   
10.     static const double shrink_factor = 1.247330950103979;
    
11.     typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    
12.     difference_type gap = std::distance(first, last);
    
13.     bool swaps = true;
    
14. 
    
15.     while ( (gap > 1) || (swaps == true) ){
    
16.         if (gap > 1)
    
17.             gap = static_cast<difference_type>(gap/shrink_factor);
    
18. 
    
19.         swaps = false;
    
20.         ForwardIterator itLeft(first);
    
21.         ForwardIterator itRight(first); std::advance(itRight, gap);
    
22. 
    
23.         for ( ; itRight!=last; ++itLeft, ++itRight ){
    
24.             if ( (*itRight) < (*itLeft) ){
    
25.                 std::iter_swap(itLeft, itRight);
    
26.                 swaps = true;
    
27.             }
    
28.         }
    
29.     }
    
30. }
    
31. 
    
32. template<typename T, std::size_t n>
    
33. T* end(T (&array)[n])
    
34. {
    
35.   return array+n;
    
36. }
    
37. 
    
38. int main() {
    
39.     int myints[] = {249, 2423, 232, 21, 1637, 35, 2556, 257};
    
40.         combsort(myints, end(myints));
    
41.         std::cout << "Sorted list/array: ";
    
42.         for(unsigned int i=0; i<8; i++)
    
43.                 std::cout << myints[i] << ' ';
    
44. }

复制代码