直插排序加强版之希尔排序算法

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

需要基础点的，大家可以看我的上一篇算法 ，直接插入排序算法。

源码：

template <class T>
int getSize(T& array)
{
    return (sizeof(array)/sizeof(array[0]));
}

int main(int argc,char *argv[])
{
    int input[] {10,12,11,2,5,78,34,64,46,32};
    int group[] {5,2,1};

    int iSize = getSize(input);
    int gSize = getSize(group);

    int span,temp,j;

    for(int m = 0;m < gSize;m++)
    {
        span = group[m];

        for(int k=0;k<span;k++)
        {
            //间隔增量 
            for(int i = k; i<iSize-span;i = i+span)
            {
                temp = input[i+span];
                j = i;
                while( j>-1 && temp < input[j])
                {
                    input[j+span] = input[j];
                    j = j-span;
                }
                input[j+span] = temp;
            }
        }

    }

    cout<<"iSize: "<<iSize<<"\ngSize: "<<gSize<<endl;
    for(auto iter = begin(input); iter!=end(input); iter++)
    {
        cout<<" "<<*iter<<" ";
    }
    return 0;
}

内部算法和直接插入算法是一样的，只是外层增量，从之前的+1 ，变成+间隔大小。

优化算法：

void swap(int &a,int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}

template <class T>
int getSize(T& array)
{
    return (sizeof(array)/sizeof(array[0]));
}

int main(int argc,char *argv[])
{
    int i,j,gap;
    int a[]{10,12,11,2,5,78,34,64,46,32};
    int n = getSize(a);

    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++)
            for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
                swap(a[j], a[j + gap]);



    for(auto iter = begin(a); iter!=end(a); iter++)
    {
        cout<<" "<<*iter;
    }
    return 0;
}

分析：理解好，将数组进行分组概念就好，之后对比方式和直接插入算法都是一样的。