希尔排序是基于插入排序的优化，如果不了解插入排序而期望直接了解希尔排序，是很难将希尔排序融汇贯通的
所以在了解希尔排序之前一定要先了解插入排序
插入排序的思想是：
1. 从数组中第二个元素（设为target）开始，将target之前的元素逐个与target对比，如果target之前的元素 大于target，那么将它后移一位，然后再向前对比，直至遇到比target小的元素,将target放在这个元素后面 (逻辑上就是将target插入到比它小的元素之前) 2.再将数组中第三个元素设为target，执行上面的操作 3.以此类推，直至到数组最后一个元素
插入排序对于基本有序的数组效率是很高的，为什么？
比如有一个数组arr=[1,2,3,5,4,6,7,8]，如果要将它升序排列，使用插入排序，只需要将4移动到5 之前就可以了，整个排序过程中，只有这一步涉及到了数组元素后移，其他的都是只有比较操作，没有移动元素 的操作，这样是非常节省时间的。 再比如有一个数组arr=[8,7,6,5,4,3,2,1]，也要将它升序排列，使用插入排序的话就是噩梦了， 因为从第二元素开始，它之前的元素都比它大，每一步都需要执行数组元素后移的操作，这就是最坏的情况。
在使用插入排序之前，如何规避掉最坏的情况，使数组趋向于最好的情况？
希尔排序就是用来完成这一任务的，希尔排序会先将一个无序的数组，逐步向有序改造，改造完成后（改造完成不等于排序完成），最后执行一次插入排序（此时排序完成）
package com.scaler7.list;
import java.util.Arrays;
public class Sort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
// 插入排序，这里不过多论述
public static void insertSort(int[] arr){
for(int i=1; i0一个作用是控制循环次数，另一个作用是和短路与结合，以防止后面的arr[i-1]数组越界
while(i>0 && arr[i-1]>target){
arr[i]=arr[i-1];
i--;
}
arr[i]=target;
}
}
// 希尔排序
public static void shellSort(int []arr){
// 最外层for循环用以控制步长gap，如何控制步长是希尔排序算法效率的关键
for(int gap=arr.length/2; gap>0; gap/=2){
// 内部for循环本质还是一个插入排序，可以对比着上面的插入排序来看
// 从第gap个数开始，运用插入排序，将数组逐步向有序改造
// 当gap为1时，内部for循环其实就和上面的插入排序一模一样了
// 所以希尔排序的最后一次是一个插入排序
for(int i=gap; i=0 && arr[j-gap]>target){
arr[j]=arr[j-gap];
j-=gap;
}
arr[j]=target;
}
}
}
}
Debgu看一下：
设立一个数组，它趋近于插入排序最坏的情况：int []arr = {9,8,7,6,5,3,4,2,1};
0.如下图，执行希尔排序之前
1.如下图，在第一次希尔排序结束之后，数组已经看起来有点那个意思了
2.如下，在第二次希尔排序之后，数组已经很像升序了，接下来将执行第三次希尔排序，此时gap为1，
也就是说第三次希尔排序其实就是插入排序，这次只需要将3插入到4前面
3.第三次希尔排序之后，数组已经有序了
