插入排序存在的问题：当需要插入的数是较小的数时，后移的次数明显增多，对效率有很大影响。

介绍：

希尔排序也是一种插入排序，是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。希尔排序是第一批突破O(n2)时间复杂度的算法之一。

理解：

为了解决插入排序中出现的问题，我们可以先让后面的和前面的进行比较，然后通过一个循环来不断减小分组的数量，如下图，到最后只剩一组时，我们便能得到一个较为好看的数组（大小相对有序）
也可以这么理解，希尔排序相当于是给数据进行了一个预处理，然后再插入排序。

image.png
image.png

实现方法

实际上希尔排序思想有两种实现方法，一种是交换法，另一种是移位法。第一种相当于预处理数据之后的冒泡排序，而第二种就是前面提到的预处理数据之后的插入排序。
交换法代码：
**public static void **shellSort(**int**[] arr){<br /> **int **temp = 0;<br /> **for **(**int **gap = arr.**length**/2;gap > 0;gap /= 2){<br /> **for **(**int **i = gap;i<arr.**length**;i++){<br /> **for **(**int **j = i - gap;j>=0;j -= gap){<br /> **if**(arr[j] > arr[j+gap]){<br /> temp = arr[j];<br /> arr[j] = arr[j+gap];<br /> arr[j+gap] = temp;<br /> }<br /> }<br /> }<br /> }<br />}
可以看到，这种方法里面出现了一个消耗大量时间的恶魔temp = arr[j];<br />arr[j] = arr[j+gap];<br />arr[j+gap] = temp;

移位法代码：
**public static void **shellSort2(**int**[] arr){<br /> _//增量gap，并逐步缩小gap<br /> _**for **(**int **gap = arr.**length**/2;gap > 0;gap /= 2){<br /> _//从第gap个元素，逐个对其所在的组进行直接插入排序<br /> _**for **(**int **i = gap;i < arr.**length**;i++){<br /> **int **j = i;<br /> **int **temp = arr[j];<br /> **if**(arr[j] < arr[j-gap]){<br /> **while **(j - gap >= 0 && temp < arr[j - gap]){<br /> _//移动<br /> _arr[j] = arr[j - gap];<br /> j -= gap;<br /> }<br /> _//当退出while后，就给temp找到插入的位置<br /> _arr[j] = temp;<br /> }<br /> }<br /> }<br />}
通过这两种方法的对比能更好地理解移位法的巧妙之处