希尔排序主要使用插入排序的思想。

插入排序更适用于元素少的情况。所以希尔排序的主要方法就是讲数组分为一个一个更小的组，然后将每个小组用插入排序的方式排序。

分组方式:现将步长设为数组长度的一半，然后每次分组减少一步。

代码：

1 void ShellSort(int* arr,int len) 2 { 3     if(arr == NULL  || len < 0) return; 4     int step ; 5     for(step = len/2;step > 0;step--)//步数变化 6     { 7         for(int i = 0;i < step;i++)//第几组 8         { 9             for(int j = i+step; j < len;j+=step)//组中循环进行插入排序10             {11                 int k = j-step;//有序的最后一个12                 int tmp = arr[j];//无序的第一个13                 while(tmp < arr[k] && k >= i)14                 {15                    arr[k+step] = arr[k];16                    k = k - step;17                 }18                 //无序元素放入19                 arr[k+step] = tmp;20             }21         }22     }23 }