shellSort
https://www.cnblogs.com/chengxiao/p/6104371.html
希尔排序，也称缩小增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。同时该算法是冲破O(n^2）的第一批算法之一，希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次比较后只能将数据移动一个位置
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
- 外层循环控制间隔的缩小，间隔gap初始为n/2，每次二分直到为1，排序完成
- 内层循环就是间隔为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;
}
}
