当我第一次听到希尔排序时，我的心里第一个蹦出来的印象是这样的 当然没有我想得那么扯。希尔排序是以其发明者Donald Shell的名字命名的。 希尔排序简单来说就是插入排序的升级版。 插入排序是一个一个的比较插入，而希尔排序则规定了一个步长gap，将a[i]与a[i+gap](或a[i-gap]）相比较进行插入排序。如下图所示 第一遍排序可得以上结果，此时将gap减小，在进行排序，直到gap=1时为止（此时就是直接插入排序）。
#include <iostream> using namespace std; void shell_sort (int* a, int len) { int i,j,temp,gap; for (gap=len/2; gap>0; gap/2) //将步长gap初定为长度的一半，并每次减半 （希尔增量序列） for (i=gap; i<len; i++) { temp=a[i]; for (j=i; j>=gap; j-=gap) if (temp<a[j-gap]) a[j]=a[j-gap]; else break; a[j]=temp; } } int main(int argc, char** argv) { int a[]={0,21,25,49,25,16,8,3,56,7,90,23}; int len =sizeof(a)/sizeof(int); //得到数组长度 shell_sort(a,len); for(int i=0; i<len; i++) cout<<a[i]<<' '; }此处说明一个希尔增量序列，是希尔本人建议的一个序列。即gap=N/2。 每次将步长减少到原来的1/2。（流行但并不好——《数据结构与算法分析》）希尔增量的选择多样，而且每一种选择都会影响到时间复杂度。 如按照写入增量序列来做，时间复杂度为O（n^2)。 运行结果如下
在这里说明：此结果只在第一次运行的输出中出现过，在此之后运行并没有输出，用dev-c++与VS结果都是没有输出。所以以上的算法仅供参考，与完全实现之间还有很大的距离。如果有大佬知道这种情况是怎么回事，请评论或私信，以便改正错误，得到最佳结果，谢谢大家。
