前言
希尔排序又称缩小增量排序，是时间效率较高的插入排序方法。
算法的基本思想：先确定一个增量d（也叫间隙gap），然后按照增量的倍数所对应的数组下标值，从待排序序列中抽取数据元素组成若干子序列，然后对子序列分别做直接插入排序，这样的操作过程就是一趟希尔排序。进行下一趟希尔排序时，先确定一个更小的增量，然后再作以上操作，直到增量为1，做最后一次直接插入排序，由于序列基本已经有序，此时只需要很少的比较和移动就可以获得有序序列。
对于图文介绍大家个可以参考这篇博客。
1. 编码
template<typename T> struct Disp
{
void operator()(T value)
{
cout << value << "\t";
}
};
void ShellSort(std::vector<int>& vec)
{
int len(vec.size());
if(len == 0) return;
cout << "display origin array:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>()); //打印原始的数据
int gap(len/2); //获得初始间隔大小
for(; gap>0; gap/=2)
{
for(int j=gap; j<len; ++j)
{
int temp = j;
while(temp-gap>=0 && vec[temp]<vec[temp-gap]) //插入排序采用交换法
{
int temp_val = vec[temp];
vec[temp] = vec[temp-gap];
vec[temp-gap] = temp_val;
//std::swap(vec, temp, temp-gap);
temp -= gap;
}
}
}
cout << "\narray sorted:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>());
}
