希尔排序

希尔排序是希尔(DonaldShell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一

思路:先取一个正整数d1’<’n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2’<’d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止。
我们来看下希尔排序的基本步骤,在此我们选择增量div=length/2,缩小增量继续以div =div/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2…1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

这里写图片描述
这里写图片描述

void shellSort(vector<int> &arry)
 {
    for(int div=arry.size()/2;div>=1;div/=2)//增量序列 
        for(int i=0;i<div;i++)//分成div组 
            for(int j=i+div;j<arry.size();j+=div)//每组进行插入排序 
                for(int k=j;k>i;k-=div)
                    if(arry[k]<arry[k-div])
                    {       
                        int t=arry[k];
                        arry[k]=arry[k-div];
                        arry[k-div]=t;
                    }
                    else
                        break;
 }

希尔排序中对于增量序列的选择十分重要,直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2…1}(希尔增量),其最坏时间复杂度依然为O(n2),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)
其余的增量序列还有Hibbard:{1, 3, …, 2^k-1},Sedgewick:{1, 5, 19, 41, 109…}该序列中的项或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1。

文章参考自:https://www.cnblogs.com/chengxiao/p/6104371.html

原文链接:加载失败,请重新获取