希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
基本思想：希尔排序把n个元素按一定的间隔分成几组，然后按组为单位进行插入排序。 。
将待排记录序列以一定的增量间隔h 分割成多个子序列，对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h ，对于每一个步长h 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体插入排序。
因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长h下每个子序列的规模都不大，用直接插入排序效率都较高。 尽管在随后的步长h递减分组中子序列越来越大，但由于整个序列的有序性也越来越明显，则排序效率依然较高。这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。
希尔算法的本质是缩小增量排序，是对直接插入排序算法的改进。
| 分类 | 排序算法 |
|---|---|
| 数据结构 | 数组 |
| 最差时间复杂度 | 根据步长序列的不同而不同。已知最好的： |
| 最优时间复杂度 | O(n) |
| 平均时间复杂度 | 根据步长序列的不同而不同。 |
| 最差空间复杂度 |
C实现：
1 void shell_sort(int src[] , int len ) 2 { 3 4 for( int k = len>>1 ; k > 0 ; k=k>>1){ 5 6 for( int m = k ; m < len ; m++){ 7 8 for( int n = m-k ; n >= 0 ; n -= k ){ 9 10 if( src[n] > src[n+k] ){ 11 12 int temp = src[n]; 13 src[n] = src[n+k]; 14 src[n+k] = temp; 15 } 16 } 17 } 18 } 19 }
C++实现：
//类型比较函数，这个是比较大的函数，当左值大于右值时返回true template< typename T> struct type_compare_bigger{ bool operator()( const T & left , const T& right){ return left > right ; } }; //类型比较函数，这个是比较小的函数，当左值小于右值时返回true template< typename T> struct type_compare_smaller{ bool operator()( const T & left , const T& right){ return left > right ; } }; //类型比较函数，这个是比较相等的函数，当左值等于右值时返回true template< typename T> struct type_compare_equal{ bool operator()( const T & left , const T& right){ return left == right; } }; const double exp_float = 0.000001; //float 类型的特化，type_compare_bigger的类型特化 template< > struct type_compare_bigger<float>{ bool operator()( const float & left , const float& right){ return (left - right) > exp_float ; } }; //float 类型的特化，type_compare_bigger的类型特化 template< > struct type_compare_smaller<float>{ bool operator()( const float & left , const float& right){ return (left - right) < -exp_float ; } }; //float 类型的特化，type_compare_bigger的类型特化 template< > struct type_compare_equal<float >{ int operator()( const float & left , const float& right){ return ((left - right) >= -exp_float) && ((left - right) <= exp_float); } }; //交换函数，如果哟需要，自己特化类型可以实现各种需求 template< typename T > struct swap{ void operator()( T* left , T* right){ T t = *left; *left = *right; *right = t; } }; //希尔排序算法部分 template< typename T , typename C = type_compare_bigger<T> ,typename S= swap<T> > struct shell_sort_algorithm{ void operator()( T src[] , array_size len ){ C comp ; S swap; for( int k = len>>1 ; k > 0 ; k=k>>1){ for( int m = k ; m < len ; m++){ for( int n = m-k ; n >= 0 ; n -= k ){ if( comp(src[n] , src[n+k]) ){ swap(src[n] , src[n+k]); } } } } } }; template <typename T> void shell_sort(T src[],array_size len) { shell_sort_algorithm<T> sso; sso(src,len); }
原文：http://www.cnblogs.com/jvane/p/4494634.html