排序算法——希尔排序

前言

希尔排序又称缩小增量排序，是时间效率较高的插入排序方法。

算法的基本思想：先确定一个增量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>());
}