希尔排序-改进版的插入排序

Shell 1959 DL.Shell

image

改进版的插入排序

增加一个间隔，每一个数据只和它前面间隔gap的数据相比较。

3个循环

假定一个gap

for(i=gap;i<arraysize;i++)
{
    for(j=gap; j>gap-1;j-=gap)
        if(array[j] < array[j-gap])
            swap(array, j ,j-gap);
}

gap的选择

half gap

    for(gap = arraysize/2; gap>0;gap/=2)
    {
        for(i=gap; i<arraysize;i++)
        {
            for(j=i;j>gap-1;j-=gap)
                if(array[j] < array[j-gap])
                    swap(array, j ,j-gap);
                else 
                    break;
        }
    }

Knuth gap

3N + 1, 效率更高

    while(h < arraysize)
    {
        h = 3*h + 1;
    }

    for(gap = h; gap>0;gap=(gap-1)/3)
    {
        for(i=gap; i<arraysize;i++)
        {
            for(j=i;j>gap-1;j-=gap)
                if(array[j] < array[j-gap])
                    swap(array, j ,j-gap);
                else 
                    break;
        }
    }

时间复杂度 平均 O(n1.3),

最好情况O(n) ，最坏O(n2)

不稳定