shellSort

https://www.cnblogs.com/chengxiao/p/6104371.html

希尔排序，也称缩小增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。同时该算法是冲破O(n^2）的第一批算法之一，希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  
• 但插入排序一般来说是低效的，因为插入排序每次比较后只能将数据移动一个位置
  

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

1. 外层循环控制间隔的缩小，间隔gap初始为n/2，每次二分直到为1，排序完成
   
2. 内层循环就是间隔为gap的插入排序，把插入排序的第二层循环中的1全部换成gap即可
   

算法步骤

template<typenameT>

voidshellSort(Tarr[],intn){

   for(intgap=n/2;gap>0;gap/=2){

       //希尔排序内部循环是插入排序，插入排序增量为1，希尔排序增量由外层循环控制

       //从第gap个元素，进行插入排序

       for(inti=gap;i<n;i++){

           Te=arr[i];

           intj;

           //对第一组的部分元素进行排序

           //希尔排序每次移动为gap，即间隔为gap

           for(j=i;j-gap>=0;j=j-gap){

               if(e<arr[j-gap])//往后移增量个

                   arr[j]=arr[j-gap];

               elsebreak;

           }

           arr[j]=e;

       }

   }

}

template<typenameT>

voidshellSort(Tarr[],intn){

   //缩小增量直到1

   for(intgap=n/2;gap>0;gap/=2)

       //从第gap个元素，逐个对其所在组进行直接插入排序操作

       for(inti=gap;i<n;i++){

           intj=i;

           inttemp=arr[i];

           //与前面的元素进行比较

           while(j-gap>=0&&arr[j-gap]>temp){

               arr[j]=arr[j-gap];

               j-=gap;

           }

           arr[j]=temp;

       }

}