在插入排序中，所有的元素都是挨个和前一个元素进行比较，并置换位置。所以交换的次数为N的平方级别。极端情况下，如果最小元素在最右侧，那么需要逐个和前面元素进行置换。如果将比较的间隔增大，那么会减少移动次数，然后逐次降低比较间隔。

于是比较的间隔的序列如下 h = 3*h+1。

代码如下：

1 #include 
     
       2  3 using namespace std; 4  5 void change(int *p,int pos1,int pos2); 6 void shellSort(int *p,int length); 7 void print(int *p,int length); 8  9 int main()10 {11     int p[] = {
   2,5,3,11,89,76,24,33,15};12     shellSort(p,sizeof(p)/sizeof(int));13     print(p,sizeof(p)/sizeof(int));14     cout << "Hello world!" << endl;15     return 0;16 }17 18 void print(int *p,int length)19 {20     for(int i=0;i
      
       =1)32     {33         for(int i=1;i
       
        =h&&p[j]
       
      
     

目前要理解shell 排序的性能仍然是个挑战，这个需要靠专家努力，但最重要的结论就是，运行时间不到N的平方级别。