希尔排序是基于插入排序的。
插入排序缺点：当一个较小的数，在数组的右侧，则需要将所有的中间数据都向右移动。
为了解决这个问题，希尔排序则是通过加大插入排序的间隔，将间隔的元素进行插入排序。为了便于理解，如下图所示有7个元素。首先计算间隔h=3*h+1，可以算出h为2，那么从第一个元素依次间隔2个元素进行插入排序，得到第二行的数组。
此时需要计算间隔的减少，就是2后面该取多少。使用h=(h-1)/3，计算出下一个h是0，则对第二行的数组进行插入排序。从而得到最终的排序结果。
当数组较大，通过将间隔的元素进行插入排序，可以使数据进行大幅度的移动，达到基本有序，即小的在左边，大的在右边，从而避免插入排序将所有的中间结果数据向右移动。