希尔排序（Shell sort）

排序思路：分组进行插入排序

先以数组长度的一半的间隔分组，各组内用插入排序；间隔减半再分组进行组内排序，直到间隔为1，再进行一次插入排序即可。

代码的实现：

//shellSort(移位法)
 for(int gap = N/2;gap > 0;gap /= 2){//划分间隔
     for(int i = gap; i < N; i++){
         int insertVal = arr[i];
         int insertIndex = i;
         while(insertVal < arr[insertIndex-gap] && insertIndex-gap>=0){
             arr[insertIndex] = arr[insertIndex-gap];
             insertIndex -= gap;
         }
         arr[insertIndex] = insertVal;
     }
 }