插入排序弱点：如果插入数值很小要交换很多次数

希尔排序算法是根据插入排序改编的

希尔排序算法优化了插入排序 

希尔排序核心思想：希尔排序通过加大插入排序之间的间隔，并对这些数据进行插入排序，当完成间隔排序后，希尔排序减少间隔再进行间隔排序。一次进行下去

间隔计算公式 h=h*3+1

间隔减少公式 h=(h-1)/3

 -------------------------------------------------------------------------------

代码实现

public static void sort(long[] arr){
  int h=1;
  //计算插入排序间隔
  while(h<arr.length/3){
   h=h*3+1;
  }
  //当间隔大于0时
  while(h>0){
   //定义中间变量保存要插入的数值
   long temp;
   //插入排序      类似插入排序 间隔改为H
   for (int i = h; i < arr.length; i+=h) {
    temp=arr[i];
    int j=i;
    while(j>h-1&&arr[j-h]>=temp){
     arr[j]=arr[j-h];
     j-=h;
    }
    arr[j]=temp;
   }
   //减少插入排序间隔
   h=(h-1)/3;
  }
 }