基础算法——希尔排序

链接地址：https://blog.csdn.net/bloke_come/article/details/126179214?spm=1001.2014.3001.5501

希尔排序可以说是插入排序的一种变种。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

O(1)

void shellInsetSort(std::vector &num, int iStep, int i)
{
    int x = num[i];
    int j = 0;
    for(j = i - iStep; j >= 0 && num[j] > x; j -= iStep)
    {
        std::swap(num[j], num[j + iStep]);
    }

    num[j + iStep] = x;
}

// 希尔排序
void shellSort(std::vector &num)
{
    int iLength = num.size();
    for(int iStep = iLength / 2; iStep > 0; iStep /= 2)
    {
        for(int i = iStep; i < iLength; ++i)
        {
            shellInsetSort(num, iStep, i);
        }
    }
}