希尔排序是基于插入排序的以下两点性质而提出改进方法的：
说说我的个人理解：
希尔排序其实就是直接插入排序的升级，原理就是先将整个待排序列按照某个增量（也称步长）分割成若干个子序列分别进行直接插入排序，然后合并，之后依次缩小增量大小在进行排序，当增量足够小（通常为1）时，再对全体元素进行直接插入排序，而此时需排序的数据几乎是已排好的了，所以此时插入排序较快。
当然如果你觉得文字比较乏味就看下面的这些例子吧
例如，假设有这样一组数 [9 1 5 8 3 7 4 6 2] ，如果我们先以步长为4进行分割，就是这样：
然后我们对每列进行排序（注意每列哦）：
将上述四行数字，依序合并我们得到： [ 2 1 4 6 3 7 5 8 9 ] 。此时2已经往前移，而8、9已经在后两位，然后再以2为步长进行分割：
继续排序：
合并得到 ［ 2 1 3 6 4 7 5 8 9］ ，此时序列已经基本有序，需交换数据的情况大为减少，这时整列进行直接插入排序效率就非常高。
最终完成排序过程，也就是步长为1时，得到最终序列为： 1 2 3 4 5 6 7 8 9 。
可能有几个步骤略难懂，这里解释下：
当 时，9和3进行了一次交换，变为 （3 9 2） (位置为1 5 9），之后在 时 ，做出的交换如上图所示（图略差...)，分为三个步骤：
步长的选取非常关键，但是步长的选择没有统一规定，也没绝对的规律。只要满足最后一个步长为1即可。Donald Shell最初建议步长选择为 ,虽然这样去可以比 类的算法更好，但仍然有减少平均时间和最差时间的余地。维基百科给出的部分步长与最坏情况下复杂度有：
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，该序列的项来自 和 这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序（后续博客整理），但是在涉及大量数据时希尔排序还是比快速排序慢。