一、希尔排序思想

希尔排序是基于插入排序的快速的排序算法，先分组后对每组进行直接插入排序，再分组再直接执行插入排序，组元素个数按照固定规则递减。最后一次分组则是一个元素即为一组通过这次插入排序后即完成排序操作。
希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序

步骤如下：

0、初始状态：arr={6,4,1,8,2,3,3,7,9,2,8}
1、按间隔为4(算法中的3*h+1得来)分组结果：
{arr[0]=6，arr[4]=2},{arr[1]=4，arr[5]=3},{arr[2]=1，arr[6]=3},{arr[3]=8，arr[7]=7}剩余{9，2，8}
2、每组使用插入排序算法进行排序（交换位置）结果：
{arr[0]=2，arr[4]=6},{arr[1]=3，arr[5]=4},{arr[2]=1，arr[6]=3},{arr[3]=7，arr[7]=8}
{2,3,1,7,6,4,3,8,9,2,8}
3、接下来按1（h=h/3）分组即最后一次的插入排序，完成。

代码如下（shell sort 00）

shellsort00.png