希尔排序是第一个算法复杂度突破 O(n^2) 的排序算法，是在插入排序的基础上做了改进，也称为缩小增量排序。希尔排序会把一个序列拆分成多个子序列，分别对多个子序列进行插入排序，然后在合并排好序的子序列，再进行整体的插入排序。子序列的拆分方法是按下标的一定增量来分组，对每一组使用插入排序进行排序，随着增量逐渐减少，每组包含的关键词逐渐增多，当增量减至1时，所有的元素都在同一个组，算法便终止。
希尔排序实现了跳跃式的比较和插入，相比直接插入排序，希尔排序针对已经排好序的数组有更优的性能。例如数组 {6,5,4,3,2,1,0} 要实现升序排列，使用直接插入排序算法，元素 0 要到数组的左端需要经过 n-1 次比较和 n-1 次移位。希尔排序把数组采用跳跃式分组，按照一定的增量把数组划分成若干组，例如假设第一次增量是2，那么数组被划分为2组，{6,4,2,0} 一组，{5,3,1} 一组，这个时候元素 0 要到数组最左端只需要比较 (n)/2 次，移动 (n)/2次 就可以了。随后逐步缩小增量，直至增量为 1，排序就完成了。
希尔排序的关键在于如何选择增量，增量的计算方式有很多种，这里使用希尔增量，即 gap=n/2 ，这样得到的增量序列为 {n/2 , (n/2)/2,…,1 }，希尔排序的增量序列的选择和证明是个数学难题，希尔增量是比较常用的，也是希尔建议的增量，但是并不是最优的。这里不再讨论最优增量。
示例：
输入 nums = {7,5,9,2,4,6,3,0,1,8} 输出 nums = {0,1,2,3,4,5,6,7,8,9}
初始数组如下图所示：
对数组按照一定增量进行分组， gap = n/2 = 10/2 = 5。这意味着数组被分为5组 {7,6}，{5,3}，{9,0}，{2,1}，{4,8}，如下图所示：
依次对分好的组使用插入排序，得到如下所示的数组：
可以看到 6，3，0，1 四个元素的位置被调前了。
然后缩小增量值 gap = 5/2 = 2，这样数组被分为2组，{6,0,4,5,2}一组，{3,1,7,9,8}一组，如下图所示：
依次对分好的两个数组使用直接插入排序，得到如下所示的数组：
然后再缩小增量值 gap = 2/2 = 1 ，这样得到最后的一个数组，其实可以看到现在的数组基本有序，只需要做微调就可以了。得到的数组如下所示：
对这个数组使用插入排序，得到最终排序号的数组：
2 编码实现public static void shellSort(int[] nums){
int gap = nums.length/2;
while(gap>=1){
for(int i=gap;i=gap&&(nums[j]
3 时间复杂度和空间复杂度
希尔排序的时间复杂度跟增量序列有关，以希尔增量为例，希尔排序的平均时间复杂度
T(n) = O(n^(3/2))。希尔排序没有额外使用空间，所以空间复杂度为 S(n) = O(1)。
